tag:blogger.com,1999:blog-3722233.post8774267375574206815..comments2024-03-18T23:13:09.570-05:00Comments on Computational Complexity: Yes Virginia, there is a Santa Clause for Complexity Theorists, If you Only BelieveLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger5125tag:blogger.com,1999:blog-3722233.post-66165743062395330612021-12-27T18:13:39.484-06:002021-12-27T18:13:39.484-06:00Because N' is nondeterministic, the brute forc...Because N' is nondeterministic, the brute force simulation would take time 2^t. Hunter Monroenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79551000746305281792021-12-13T01:08:33.636-06:002021-12-13T01:08:33.636-06:00Now I did, and I think I can understand (*). What ...Now I did, and I think I can understand (*). What I don't understand is, why it doesn't contradict the existence of a universal TM. That could simply run N' on x' for t steps and the simulation only takes a polynomial amount of time in t.<br /><br />ps. Instead of leaving a new comment, please reply to mine, and then I'll get notified. Now a week passed before I've again accidentally stumbled into this...domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61936124562747798152021-12-06T22:10:19.719-06:002021-12-06T22:10:19.719-06:00Thanks for the "Swiss army knife" ping; ...Thanks for the "Swiss army knife" ping; I enjoyed the conjecture spin of the software toolkit version analogy ... will take a look at things.EGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47702163686575548452021-12-06T13:33:42.846-06:002021-12-06T13:33:42.846-06:00In words, it says that for any Turing machine M ac...In words, it says that for any Turing machine M accepting the TMs that do not halt within t steps, there is one family of inputs for M indexed by t which is hard for M, that is the running time of M on that family is superpolynomial in t. Have you looked at the discussion paper https://speedupblogger.wordpress.com/2021/12/05/unifying-conjectures-on-complexity-and-noncomputability/ and the Theoretical Computer Science paper https://arxiv.org/abs/0906.3765? Are you saying the statement is imprecise or hard to interpret?Hunter Monroenoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-62392571593742408422021-12-06T01:56:06.040-06:002021-12-06T01:56:06.040-06:00I couldn't understand (*).I couldn't understand (*).domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com