tag:blogger.com,1999:blog-3722233.post4220371009343546487..comments2023-03-29T09:38:56.563-05:00Comments on Computational Complexity: An application of Ramsey Theory to Proving Programs TerminateLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger14125tag:blogger.com,1999:blog-3722233.post-28721607166987438232011-08-29T23:45:19.260-05:002011-08-29T23:45:19.260-05:00Ohh and I also should add that there any true \Pi_...Ohh and I also should add that there any true \Pi_2 statement will be a useful way to prove some program is total (the one that takes as input the \forall variable and then terminates on verifying the existential). So it's not clear what makes Ramsey theory special here.TruePathhttps://www.blogger.com/profile/09101368178633477827noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38746888587501687172011-08-29T23:42:45.788-05:002011-08-29T23:42:45.788-05:00For a famous example where you really need the Inf...For a famous example where you really need the Infinite Ramsey Theorem consider the Paris Harrington Theorem. There is a program which halts on every integer (coded triple of integers) iff the strengthed Ramsey theorem holds for that triple. This is not provable in PA but is deducible from the Infinite Ramsey Theorem.<br /><br />So sometimes you really really do need Ramsey theory or at least principles of infinitary reasoning.<br /><br /><br />---<br /><br />It's much easier to go from the Infinite Ramsey Theorem to the Finite Ramsey Theorem using Koneig's Lemma. As standard we number the vertices with non-negative integers and fix a bijection taking the set {x,y} to a non-negative integer.<br /><br />Fix k and let T be the set of finite sequences of integers from 0..c-1 viewed as colorings of the associated edges that don't witness the existence of a homogeneous set of size k. T is a finitely branching tree and by the infinite ramsey theorem it can't have an infinite path so by Koneig's Lemma T is finite and thus has a longest string in it. That length is at least RT(k,c).<br /><br />Of course things get funny if you do reverse math and don't assume WWKL0<br /><br />---TruePathhttps://www.blogger.com/profile/09101368178633477827noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-6863707186671567132011-08-21T10:45:23.116-05:002011-08-21T10:45:23.116-05:00sorry for being completely offtopic,
I have a gene...sorry for being completely offtopic,<br />I have a general question about NP reductions, is there a book or another collection out there covering let us say the 300 most important reductions ever published. According to wikipedia there are more than 3000 known NP problems, so a complete survey is quite infeasible, but many of the 3000 poblems may be just specialised versions of standard problems. What I'd really like to have atm, is a collection of reductions from Karps 21 problems to each other (where feasible) or at least to 3-SAT, CLIQUE, DHC/HC/TSP, which I consider the most basic NP problems. Most text books just do a few reductions in form of a chain ususally ending with 3-SAT or CLIQUE, which doesn't give you a hint how to do another reduction. Of course you could just "insert" one reduction into another, but this usually leads to hopelessly bloated situations and almost always there are different and/or much more efficient ways, hence my question.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5586620547628459572011-08-17T12:40:41.238-05:002011-08-17T12:40:41.238-05:00The claim "either wi < wj or xi < xj&qu...The claim "either wi < wj or xi < xj" also yields termination by Dickson's Lemma.Sylvainhttps://www.blogger.com/profile/05888158547954503588noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-91475949882495154052011-08-16T14:33:13.079-05:002011-08-16T14:33:13.079-05:00Re: twitter post on instant fame vs. long-term suc...Re: twitter post on instant fame vs. long-term success.<br /><br />However, in academia if you get instant fame for something, then you get tenure. So it's quite different from the opera world, where if you are "over the hill" you could be unemployed.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37956385316587404052011-08-15T17:45:25.970-05:002011-08-15T17:45:25.970-05:00There is also a set-theoretic way of looking at it...There is also a set-theoretic way of looking at it: Consider the lexicographic order for (w,x,y). It is a well-ordering, and in every iteration of the program you get a triple lower in the order. Hence the program halts on account of having no infinite decreasing sequence over a well ordered set. This would work also for more variables (and so would the Ramsey proof).Eldarnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39059506090778706362011-08-15T16:50:42.956-05:002011-08-15T16:50:42.956-05:00Actually, ignore that last comment. Of course it ...Actually, ignore that last comment. Of course it didn't make any sense -_-Sam Alexanderhttp://www.xamuel.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-80888619436341162522011-08-15T16:48:12.013-05:002011-08-15T16:48:12.013-05:00Re: garethrees: the variable y plays one importan...Re: garethrees: the variable y plays one important role: it rules out the most obvious proof attempt, which would be to show the sum x+w decreases every time. Pesky y, messing that all up!Sam Alexanderhttp://www.xamuel.comnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75146500793722631622011-08-15T14:40:21.785-05:002011-08-15T14:40:21.785-05:00garethrees.org- Yes, y is a red herring- the examp...garethrees.org- Yes, y is a red herring- the example<br />is supposed to be ... an example to make the point<br />To see more real examples (hmmm- not sure its THAT real)<br />see their papers or my exposition.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-55374425854355775682011-08-15T14:24:39.340-05:002011-08-15T14:24:39.340-05:00What role does the variable y play in this argumen...What role does the variable y play in this argument? (Is it a red herring?)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13009114318053014512011-08-15T13:49:06.499-05:002011-08-15T13:49:06.499-05:00Anon- Thanks, fixed.Anon- Thanks, fixed.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61790915343802376072011-08-15T13:18:15.189-05:002011-08-15T13:18:15.189-05:00A typo: A. Rybalachenko is missing in your referen...A typo: A. Rybalachenko is missing in your reference [1] (I talk about the pdf)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79474468245647572782011-08-15T12:22:07.529-05:002011-08-15T12:22:07.529-05:00Typo- should have been control=input(1,2).
I have ...Typo- should have been control=input(1,2).<br />I have fixed it.<br />Thank you for the correction.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3411525047822144372011-08-15T12:18:05.164-05:002011-08-15T12:18:05.164-05:00What if the user enters "3" every time?What if the user enters "3" every time?Anonymousnoreply@blogger.com