tag:blogger.com,1999:blog-3722233.post69669537668563722..comments2024-03-02T02:08:38.816-06:00Comments on Computational Complexity: A non rigorous proof techniqueLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-3722233.post-38748257089800826702010-11-07T09:24:26.329-06:002010-11-07T09:24:26.329-06:00Anonymous posts: "Faculty position at UPenn i...Anonymous posts: <i>"Faculty position at UPenn in "Market and Social Systems Engineering"</i><br /><br />GASARCH's post seemed to me to be a "Great Truth" post, in the sense that the <i>opposite</i> assertion is <i>also</i> a great truth. To see this, let's split GASARCH's heuristic in two:<br /><br />--------------------<br /><b>The Principle of Proof Conservatism:</b> "If that proof was right, I would have known about it."<br />--------------------<br /><b>The Principle of Axiom Activism:</b> "If those postulates were wrong, I wouldn't have known about it."<br />--------------------<br /><br />As a concrete example, let's recall a few historical reasons why the applicant for the above faculty position should embrace "Axiom Activism" (which might also be called "Postulate Progressivism"):<br /><br />--------------------<br /><i>Non-euclidean geometry: </i> "If Euclid's parallel postulate were disposable, then I would know that."<br />--------------------<br /><i>Control theory: </i> "If control (rather than efficient flapping) were the key to powered flight, then I would know that."<br />--------------------<br /><i>Computer science: </i> "If machines (rather than human computers) were the key to numerical computation, then I would know that."<br />--------------------<br /><i>Genomics: </i> "If robots (not lab technicians) were key to genomic experiments, then I would know that."<br />--------------------<br /><i>Enterprise: </i> "If reliable and efficient simulation algorithms were the key to initiating large-scale enterprises, then I would know that."<br />--------------------<br /><br />As Yogi Berra, Niels Bohr, Casey Stengel, Dan Quayle, Mark Twain, Will Rogers, Winston Churchill, Albert Einstein, G. B. Shaw, Disraeli, Confucius, and Freeman Dyson (and many more) all are reputed to have said: "Predictions are hard, especially about the future" ... yet nonetheless I will suggest that the following progressive postulates are likely to emerge in the 21st century:<br /><br />--------------------<br /><i>Progressive Complexity Theory : </i> "P and NP are <i>not</i> the most natural classes for studying computational complexity."<br />--------------------<br /><i>Progressive QIT: </i> "Coherent flows are <i>not</i> the most natural instantiations of classical and quantum dynamical processes."<br />--------------------<br /><br />In short, the history of the STEM enterprise in the 19th and 20th centuries suggests that GASARCH's heuristic can reasonably be generalized and broadened to a principle that has been respected throughout history by great mathematicians, scientists, engineers, and enterprises: "Respect theorems, but not postulates."John Sidleshttp://www.mrfm.orgnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38921686226046692192010-11-06T12:06:02.729-05:002010-11-06T12:06:02.729-05:00Faculty position at UPenn in "Market and Soci...Faculty position at UPenn in "Market and Social Systems Engineering": http://jobs.acm.org/c/job.cfm?site_id=1603&jb=7249905<br /><br />"focused on topics at the burgeoning intersection of systems engineering, operations research, game theory and mechanism design, algorithmic aspects of economics and sociology, and many related areas. "Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-57039381613904334512010-11-05T10:00:17.593-05:002010-11-05T10:00:17.593-05:00Faculty position at Duke: http://www.cs.duke.edu/d...Faculty position at Duke: http://www.cs.duke.edu/department/resources/openings.php<br /><br />Ad lists "Algorithms" and "Computational Economics" as areas of interest.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-82313157396320518652010-11-04T20:53:57.376-05:002010-11-04T20:53:57.376-05:00Xamuel- Great, thanks again.
I have heard that in...Xamuel- Great, thanks again.<br /><br />I have heard that in recursion theory<br />sets TEND to be Turing-complete<br />unless you MAKE THEM not Turing-complete. Your example is an...<br />example of this.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73679425249213745892010-11-04T19:07:48.229-05:002010-11-04T19:07:48.229-05:00"Lets call your set X.
Now the question arise..."Lets call your set X.<br />Now the question arise: is X equivalent<br />to HALT? I suspect either YES or<br />it may depend on the actual programming system you are using. I suspect that for any ``natural'' programming system<br />(not sure how to define that) the answer is yes."<br /><br />One way to make the set more precise is to clarify that when we say a set T is "decidable", we mean there exists a total computable function f such that f(n)=1 iff n is in T.<br /><br />And then, define X to be the set such that n is in X iff f(n)!=1 (or f(n) doesn't halt), where f is the nth (not-necessarily-complete) computable function, which you can determine however you like, e.g., the function whose C code's binary representation is n. (The smarty-farty keyword to use here is "Godel number")<br /><br />In that case, X is equivalent to HALT. Given HALT, deciding X is easy. Conversely, to determine whether a TM M halts, let M' be the machine which runs M and then, if that ever finishes, outputs 1. Then M halts iff M' ouputs 1 iff n is outside X where n is the number of the function computed by M'.Xamuelhttp://www.xamuel.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49834076103200163032010-11-04T12:57:43.481-05:002010-11-04T12:57:43.481-05:00My apologies from Peter Gac, if he exists, but may...My apologies from Peter Gac, if he exists, but maybe you wanted to write Gacs.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45045886798663424692010-11-04T12:34:27.732-05:002010-11-04T12:34:27.732-05:00Xamuel. Thanks!
Lets call your set X.
Now the que...Xamuel. Thanks!<br /><br />Lets call your set X.<br />Now the question arise: is X equivalent<br />to HALT? I suspect either YES or<br />it may depend on the actual programming system you are using. I suspect that for any ``natural'' programming system<br />(not sure how to define that) the answer is yes.<br /><br />GASARCHGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-36698256779239139802010-11-04T12:14:10.862-05:002010-11-04T12:14:10.862-05:00"It was the only proof I knew of that a set w..."It was the only proof I knew of that a set was undecidable that did not use HALT (are there others?) "<br /><br />Yes, there is a trivial example. Let S be the set defined by saying n is in S iff n is not in the nth decidable set. Then S is non-decidable by the usual diagonalization argument.Xamuelhttp://www.xamuel.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90062279682112899712010-11-04T12:10:44.655-05:002010-11-04T12:10:44.655-05:00On one of those PBS "GED" shows I saw th...On one of those PBS "GED" shows I saw them "prove" that pi was equal to exactly 22/7. On that day I lost respect for PBS and began to question the lessons taught by Bert and Ernie as well.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76883560542779299652010-11-04T11:55:26.284-05:002010-11-04T11:55:26.284-05:00YES, THANKS!
I have fixed it.
GASARCHYES, THANKS!<br />I have fixed it.<br /><br />GASARCHGASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-76624879725995780122010-11-04T11:12:10.446-05:002010-11-04T11:12:10.446-05:00There might be a typo when you wrote C_s instead o...There might be a typo when you wrote C_s instead of C_{s_0} in line 2 of the proof of Theorem 5.2. Or maybe you meant that statement to start "Find s_0 such that for all s >= s_0, ..."Dave Dotyhttp://www.dna.caltech.edu/~ddoty/noreply@blogger.com