tag:blogger.com,1999:blog-3722233.post5543423800846639770..comments2024-03-28T18:17:00.135-05:00Comments on Computational Complexity: Is P=?NP ind of ZFC a respectable viewpoint?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-3722233.post-24295737738049068282009-09-04T10:19:18.935-05:002009-09-04T10:19:18.935-05:00There is recent paper from two brazilian logicians...There is recent paper from two brazilian logicians on the independence of P vs NP:<br /><br />COSTA, N. C. A. ; DORIA, F. A. ; BIR, E. . On the Metamathematics of the P vs. NP question. Applied Mathematics and Computation, v. 189, p. 1223-1240, 2007.<br /><br />I would like to know if someone has read this paper and what are the opinions about it.Igor Carboninoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77235371793073436132009-09-04T09:00:33.527-05:002009-09-04T09:00:33.527-05:00It's also relevant to ask set theorists what t...It's also relevant to ask set theorists what they think! Because of the arithmetical nature of P vs NP, I think that an overwhelming majority would say that it is not a question of major interest to set theory (that is, of interest beyond its general importance in all of mathematics). However, there are two counterpoints to this. <br /><br />First, the methods of set theory are not necessarily irrelevant. For example, the relativization results of Baker, Gill, and Solovay (the last being a major figure in set theory) were inspired by forcing. However, this is not relevant to the independence of P = NP from ZFC.<br /><br />Second, the large cardinal hierarchy is a standardized benchmark for measuring the consistency strength of strong theories. If P = NP turns out to have such strength, then fitting it in this hierarchy becomes a very interesting question. However, there is currently no evidence that P = NP has such strength.François G. Doraishttps://www.blogger.com/profile/00114836660380423908noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-49473055408657457612009-09-04T06:46:44.786-05:002009-09-04T06:46:44.786-05:00Is P=?NP a simple mathematical question? That is, ...Is P=?NP a simple mathematical question? That is, if for example someone proves that P=?NP is ind. of ZFC, is the problem solved? Because it remains interesting to know if there exists a polynomial algorithm for SAT (for example).B.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-46749102141088447592009-09-03T17:04:23.286-05:002009-09-03T17:04:23.286-05:00Marginally related: I remember a conversation with...Marginally related: I remember a conversation with a friend from a while back..<br /><br />"You cannot dismiss this right away. Some serious mathematicians worked on it."<br /><br />"Well, yes, but they weren't serious when they did it."Mihaihttps://www.blogger.com/profile/11599372864611039927noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-3344972523141154552009-09-03T14:13:37.988-05:002009-09-03T14:13:37.988-05:00Without knowing anything, it is respectable to ask...Without knowing anything, it is respectable to ask whether P vs NP independent of ZFC. There are plenty of standard questions in mathematics for which it's not all that respectable, because the motivations are clear evidence that it isn't. Independence from ZFC can be viewed as the math student's version of the Anthropic Principle. But complexity theory is a fellow traveller of logic, so it's a little different.<br /><br />That said, it sounds like if you do know something, there is significant evidence that it isn't independent of ZFC. So the right thing to do in Wikipedia is to explain that evidence.Greg Kuperberghttps://www.blogger.com/profile/16655664043505766628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-58784335819437026542009-09-03T13:59:54.913-05:002009-09-03T13:59:54.913-05:00Scott Aaronson has a nice survey and discussion on...Scott Aaronson has a nice survey and discussion on the topic. <br /><a rel="nofollow">http://scottaaronson.com/papers/pnp.pdf</a>Jeremy Hhttps://www.blogger.com/profile/14193871564985626500noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63096671756651203792009-09-03T13:45:16.717-05:002009-09-03T13:45:16.717-05:00This is my fault, I think — someone was trying to ...This is my fault, I think — someone was trying to make a separate section in <a href="http://en.wikipedia.org/wiki/P_%3D_NP_problem" rel="nofollow">the Wikipedia article on P vs NP</a> and <a href="http://en.wikipedia.org/w/index.php?title=P_%3D_NP_problem&diff=310553973&oldid=310506776" rel="nofollow">I cut it back</a>.<br /><br />My opinion is <a href="http://en.wikipedia.org/w/index.php?title=Talk:P_%3D_NP_problem&curid=7493&diff=310797192&oldid=310796394" rel="nofollow">here</a>: it should be mentioned in the article, but not out of proportion to its importance to mainstream complexity theorists. So I am also interested in the answer to your sociology question.D. Eppsteinhttp://en.wikipedia.org/wiki/User:David_Eppsteinnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-66235641633500813042009-09-03T13:44:15.623-05:002009-09-03T13:44:15.623-05:00If P!=NP is independent of Peano Arithmetic, then ...If P!=NP is independent of Peano Arithmetic, then "almost" P=NP. This is a simple argument, and the proof is in: http://www.cs.technion.ac.il/~shai/ph.ps.gz<br /><br />(Ben-David, S., and Halevi, S., "On the Independence of P versus NP", Technion, TR 714, 1992.)<br /><br />I.I.noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85992445655615636242009-09-03T13:21:58.361-05:002009-09-03T13:21:58.361-05:00Schoenfield Absoluteness gives some limitation. I...Schoenfield Absoluteness gives some limitation. In particular, since P=NP is definable in PA, it is Delta^1_1, and thus absolute for all inner models of ZF+DC (and, a fortiori, ZFC). So there are quite a lot of forcing constructions that cannot prove it independent. <br /><br />I'm sure Harvey Friedman has thought about whether a large cardinal extension could change the truth of P=NP, but I don't remember hearing any results.Unknownhttps://www.blogger.com/profile/05967102590838998093noreply@blogger.com