tag:blogger.com,1999:blog-3722233.post3501776212238109913..comments2024-03-29T08:55:55.727-05:00Comments on Computational Complexity: 75 Years of Computer ScienceLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-75605169739272201522011-06-01T09:08:18.773-05:002011-06-01T09:08:18.773-05:00To phrase the above question more formally (althou...To phrase the above question more formally (although I'm no expert), we know from the work of Juris Hartmanis (and from the explicit construction provided on TCS StackExchange by Emanuele Viola) that there exist Turing machines M whose runtime is in P, and yet the natural question "Is the runtime exponent of M less than a given value k?" is undecidable for these machines.<br /><br />Then a similarly natural follow-on question, whose answer is (AFAICT) <i>not</i> known, is "Do there exist languages L that are recognized solely by those Turing machines in P whose runtime exponents are undecidable? And can examples of these machines and languages be finitely constructed?"<br /><br />Needless to say, such Turing machines would be very interesting from a fundamental point-of-view, and concrete instantiations of them (or the provable infeasibility of constructing them) might be interesting too from a cryptographic point-of-view ... as examples of algorithms for which (by construction) natural questions like "How does this algorithm work?" or even verification questions like "Is this algorithm working correctly?" have no natural answers. <br /><br />As for questions relating to the validation of sampling from distributions ... these questions seem to be even harder ... and yet they have considerable fundamental and practical importance.<br /><br />Pointers to articles/monographs/textbooks discussing these issues would be very welcome ... Juris Hartmanis' monograph <i>Feasible computations and provable complexity properties</i> (1978) is the best I have found to date.<br /><br />Very broadly speaking, these questions help us appreciate why so much of complexity theory is oracle-dependent. When Turing chose the fateful word "possible" instead of "verifable" in asking “What are the possible processes which can be carried out in computing a number?”, he implicitly embedded oracles into the foundations of computational complexity theory ... and thereby created great problems for mathematicians and engineers alike.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18255907062702901952011-05-31T14:50:09.412-05:002011-05-31T14:50:09.412-05:00Yes, by "verifiably correct" that is wha...Yes, by "verifiably correct" that is what I mean ... it was eye-opening to me to learn from TCS StackExchange .. via the question "Are runtime bounds in P decidable? (answer: no)" ... that verification procedures that we engineers take for granted—like "What is the runtime exponent for this code?"—are generically undecidable (these theorems go back to the work of Juris Hartmanis in the 1970s and 1980s).<br /><br />This same topic arose on MathOverflow in association to Gil Kalai's topic "What notions are used but not clearly defined in modern mathematics?" specifically with regard to the question <a href="http://mathoverflow.net/questions/56677/what-notions-are-used-but-not-clearly-defined-in-modern-mathematics/57123#57123" rel="nofollow">"What properties of P are not decidable in modern mathematics?"</a><br /><br />The list of P's undecidable properties is surprisingly long, and contains some surprising members. For some purposes, would computer science be better off working with a restrictive subclass of P and a shorter list of undecidable properties?John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-41081004488899642232011-05-31T14:05:49.180-05:002011-05-31T14:05:49.180-05:00> What are verifiable processes in this differe...> What are verifiable processes in this different question?<br /><br />I guess he means that the algorithm is not only correct but provably correct and not only polynomial-time but provably polynomial-time (conceivably, there could be polynomial-time algorithm for SAT that we cannot prove to be correct and we cannot prove to be polynomial-time). I am not sure if it makes any real difference.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60848394230284799892011-05-31T13:28:27.029-05:002011-05-31T13:28:27.029-05:00What are verifiable processes in this different qu...What are verifiable processes in this different question?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51503026274576272552011-05-30T20:32:18.862-05:002011-05-30T20:32:18.862-05:00I have often wished that Turing had soberly asked:...I have often wished that Turing had soberly asked: “What are the <i>verifiable</i> processes which can be carried out in computing a number?” ... <br /><br />... instead of Turing asking the fatefully harder question: “What are the <i>possible</i> processes which can be carried out in computing a number?” <br /><br />The point being, that in our present-day world we understand very little about even so basic a class as P ... a class (AFAICT) whose membership and run-time ordering both are Turing-undecidable.<br /><br />In the "sober-minded Turing" alternative universe, we might by now (with hard work and luck) have proved that verifiable-P (vP) and verifiable-NP (vNP) satisfy vP≠vNP ... whereas in our present universe we are not close at all (most folks think) to a proof that possible-P (pP) and possible-NP (pNP) satisfy pP≠pNP <br /><br />Hmmm ... would a proof of vP≠vNP be satisfying to mathematicians who now have spent two generations attempting to prove pP≠pNP?John Sidleshttp://sidles@u.washington.edunoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18534484923267855692011-05-28T22:03:05.555-05:002011-05-28T22:03:05.555-05:00Rasmus: Yes. If you read Computing Machinery and ...Rasmus: Yes. If you read <i>Computing Machinery and Intelligence</i>, Turing talks explicitly about randomized algorithms, and in a remarkably modern way.Scotthttps://www.blogger.com/profile/13456161078489400740noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37395803068662566272011-05-28T18:43:48.507-05:002011-05-28T18:43:48.507-05:00I don't know about Turing, but randomized (num...I don't know about Turing, but randomized (numerical) algorithms date back at least to Metropolis and Ulam "The Monte Carlo Method", JASA 1949.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3641029299578646292011-05-28T17:46:05.692-05:002011-05-28T17:46:05.692-05:00Does anyone know if Turing ever considered randomi...Does anyone know if Turing ever considered randomized computation? For example, arguing that randomized computation can be simulated by deterministic computation? Were there any randomized algorithms known 75 years ago? E.g. testing polynomial identity by evaluation in sufficiently many points?Rasmus Paghhttps://www.blogger.com/profile/05722627403861422993noreply@blogger.com