tag:blogger.com,1999:blog-3722233.post3991203276322745177..comments2020-07-02T09:25:12.852-04:00Comments on Computational Complexity: Why do we think P NE NP? (inspired by Scott's post)Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger18125tag:blogger.com,1999:blog-3722233.post-57859428177886574032020-01-07T02:17:06.491-05:002020-01-07T02:17:06.491-05:00Dear William Gasarch,
Happy New Year!
Since you ...Dear William Gasarch,<br /><br />Happy New Year!<br /><br />Since you talk of « Kuhn-light », we may look at the P vs NP problem from another perspective :<br /><br />There exist mainly two opinions about the P vs NP problem: P = NP and P /= NP (P NE NP), and most people think P /= NP (see Gasarch’s second poll [1]).<br /><br />As known, there exist two popular definitions of NP which are considered to be equivalent [2][3] : <br />Definition 1 : NP is the class of problems decidable by NDTM (NonDeterminisitic Turing Machine) in polynomial time. <br />Definition 2 : NP is the class of problems verifiable by TM (Turing Machine) in polynomial time. <br /><br />If it is indeed P /= NP, it means that NP is completely different from P, then the P vs NP problem may involve some profound conceptual issues. Therefore, we can ask: <br />Are these two popular definitions of NP consistent with the reality?<br /><br />In other words, we ask: <br />Q1: What is NP?<br />Q2: Can « NP is the class of problems decidable by NDTM in polynomial time » be the definition of NP?<br />Q3: Can « NP is the class of problems verifiable by TM in polynomial time » be the definition of NP?<br /><br />Yu LI<br /><br />Reference :<br />[1] William I. Gasarch, The P=?NP poll. SIGACT News Complexity Theory Column 74. http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf<br />[2] https://en.wikipedia.org/wiki/NP_(complexity)#Equivalence_of_definitions<br />[3] Sipser's Introduction to the Theory of Computation, section 7.3.<br />liuyu2205https://www.blogger.com/profile/00716073073296092253noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75528612980943405162020-01-06T10:05:46.177-05:002020-01-06T10:05:46.177-05:00Sorry for the late response- I was just browing th...Sorry for the late response- I was just browing this old post for some reason and came upon your comment that I must have missed back in 2017. <br />Anyway, I think the problem of amicable numbers- given x,y<br />is it the case that the factors of x add up to y and vice versa<br />was in BPP but I THINK is now in P.<br /><br />however, the fact that this is the ONE problem I can think of and I may even be wrong shows that YES, there are VERY FEW<br />problems in BPP in the first place. <br /><br />GASARCHhttps://www.blogger.com/profile/03615736448441925334noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-68962182622679275442017-05-07T18:11:35.665-04:002017-05-07T18:11:35.665-04:00"P=BPP. Almost every problem in BPP ended up..."P=BPP. Almost every problem in BPP ended up falling into P over time" PLEASE TELL ME WHICH NON-TRIVIAL PROBLEM OTHER THAN PRIMES (WHICH ALREADY HAD A P ALGORITHM ASSUMING GRH) LANDED UP IN P FROM BPP?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88438524487716892802014-03-23T14:37:54.082-04:002014-03-23T14:37:54.082-04:00I still like to think about these sorts of problem...I still like to think about these sorts of problems regardless because they do form something to think about to generate ideas. One thing that is fun to think about is that while it is hard to find the best path, it is relatively easy to find a least squares circle that passes by each point such that the residuals can be minimized. One can think also in terms of projections on independent axis, which automatically has an ordering on that axis. There are all sorts of ways to look at the problem that make the problem interesting to think about if not work on, which is probably why it gets a lot of interest, even if some of the claims about what P=NP would mean are overstated some times.<br /><br />http://thefurloff.com/2014/03/23/golden-tickets-teotwawki-radio-k-a-o-s/Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-61740901023289263182014-03-20T05:44:35.326-04:002014-03-20T05:44:35.326-04:00Just like Dr Lipton, I am also "just open&quo...Just like Dr Lipton, I am also "just open" to the possibility P=NP, saying that its chances and those of P!=NP should be taken comparable if one is not prejudiced. This is also how my view was (correctly) represented by Scott Aaronson (in his otherwise demagogic, untrue, insulting, and generally idiotic rant).Luboš Motlhttps://www.blogger.com/profile/17487263983247488359noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-39986020614041062182014-03-15T19:53:36.788-04:002014-03-15T19:53:36.788-04:00My understanding is that, as David said, Dana prov...My understanding is that, as David said, Dana proved the result modulo one missing piece in 2011 (http://eccc.hpi-web.de/report/2011/112/). Dinur and Steurer later filled in the missing piece. The paper Gasarch linked to is the journal version of Dana's paper, which explains the whole history and which credits Dinur-Steurer.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38297362738524086732014-03-14T15:22:24.058-04:002014-03-14T15:22:24.058-04:00Followup The above considerations have been formu...<b>Followup</b> The above considerations have been formulated as one answer (of several posted) to Scott Aaronson's <i>MathOverflow</i> question/request for "Analogues of P vs. NP in the history of mathematics,", <b><a href="http://mathoverflow.net/a/160349" rel="nofollow">that answer being</a></b>:<br /><br />• <i>The Runtime Fence Problem for TMs</i> which Emanuele Viola proved is undecidable, and by extension<br /><br />• <i>The Runtime Fence Problem for Languages</i> which is natural, open, apparently difficult, and conjecturally undecidable. <br /><br /><i>Computational Complexity</i> readers who can supply further answers to Scott's well-asked question/request, please post them.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86695795034478278302014-03-14T14:25:09.017-04:002014-03-14T14:25:09.017-04:00Ya, what is the story here? Dinur and Steurer also...Ya, what is the story here? Dinur and Steurer also claim the set cover result as their own, and their arxiv paper (http://arxiv.org/abs/1305.1979v2) is from May, which significantly predates Dana's December revision. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-74706524374185157232014-03-14T10:12:01.871-04:002014-03-14T10:12:01.871-04:00Postscript In particular, the TCS StackExchange q...<b>Postscript</b> In particular, the <i>TCS StackExchange</i> question <b><a href="http://cstheory.stackexchange.com/questions/11691/does-p-contain-languages-whose-existence-is-independent-of-pa-or-zfc-tcs-commu" rel="nofollow">Does P contain languages whose existence is independent of PA or ZFC? (answer: not known)</a></b> was converted to an open community wiki precisely to encourage sustained mathematical discourse relating to PvsNP, regarding which the opinions of complexity theorists have been so notably (and wonderfully!) diverse for two generations. <br /><br />A respectable cohort of CT luminaries already has commented upon the above question, and further comments (and even entire proposed answers) are welcomed needless to say. <br /><br />So if you've got an answer, post it!<br /><br />It was Scott Aaronson who suggested <i>TCS StackExchange</i> as an appropriate venue for open, reasoned, civil discussions of PvsNP questions. That was well done, Scott.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13969110277193752402014-03-14T09:21:20.629-04:002014-03-14T09:21:20.629-04:00What is your opinion of Paradox Recognition:
1. d...What is your opinion of Paradox Recognition:<br /><br />1. decidable.<br />2. Semi-decidable.<br />3. Undecidable.<br />4. Paradoxical.<br /><br />Established belief since the 1930s is that it is an undecidable.problem, while any student kid can write a trivial program to decide it. This is why Scott is banning the above proof.<br /><br />best,<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-72547946600288369462014-03-13T21:58:49.101-04:002014-03-13T21:58:49.101-04:00Reasons associated to the (plausible) undecidabili...Reasons associated to the (plausible) undecidability of PvsNP are summarized in the following <i>TCS StackExchange</i> answer:<br /><br />• "Are runtime bounds in P decidable? (answer: no)"<br /><br />and in the following <i>TCS StackExchange</i> community wikis:<br /><br />• "Does P contain languages whose existence is independent of PA or ZFC? (answer: not known)"<br /><br />• "Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)" <br /><br />As Scott Aaronson aptly says "The border [between complexity classes] traces out weird and jagged shapes." To the best of present complexity-theoretic knowledge, the "shape" of the borders between oracle-defined complexity classes plausibly is so "weird and jagged" that (in general) class membership is undecidable.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2287149660849467292014-03-12T14:17:29.525-04:002014-03-12T14:17:29.525-04:00It took 350 years for FLT to be proven. New math ...It took 350 years for FLT to be proven. New math was invented trying to prove it. One clever approach that has not yet been considered ends it all.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29061023747391733022014-03-11T10:56:52.634-04:002014-03-11T10:56:52.634-04:00Just to clarify the result about set cover hardnes...Just to clarify the result about set cover hardness, in an APPROX 2012 paper Moshkovitz showed that if a certain conjecture was true, then it is NP-hard to approximate set cover within ln n. In an upcoming STOC 2014 paper, Dinur and Steurer show (among other results) that a weakened form of the conjecture is true, and this is enough to imply the set cover result. The Moshkovitz paper which is pointed to in the blog post is a recently updated version of the APPROX paper which now notes that the result of the Dinur-Steurer paper allows the proof of the result. David P. Williamsonhttp://www.davidpwilliamson.net/worknoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-10613138479853213652014-03-11T06:58:41.961-04:002014-03-11T06:58:41.961-04:00Theorem: P=NP <==> P!=NP.
Proof: The Kleen...Theorem: P=NP <==> P!=NP.<br /><br />Proof: The Kleene-Rosser paradox is a counter-example to NP-completeness.<br /><br />================================================<br /><br />Step 1. Cook_Levin: For all w in L in NP, <br />M accepts w <==> \exists A(w)=SAT.<br /><br />Step 2. Assume M_KR Kleene-Rosser Paradox Recognizer Turing machine, then:<br />M_KR accepts w_KR <==> e^-1(w_KR)= NOT e^-1(w_KR).<br /><br />Step 3. Put M=M_KR and w=w_KR.<br /><br />==> L.H.S. of (1) = L.H.S. of (2).<br /><br />==> R.H.S. of (1) = R.H.S. of (2).<br /><br />==> There is no SAT(w_KR).<br /><br />==> L_KR={w_KR_i} is in NP and NOT NP-complete.<br /><br />==> L_KR is a counter-example for NP-completeness.<br /><br />==> SAT is (NOT) NP-complete.<br /><br />==> SAT is NP-complete <==> SAT is (NOT) NP-complete,<br /> Cook's proof is still correct despite the contradiction.<br /><br />==> P=NP <==> P!=NP.<br />================================================<br /><br />best,<br /><br />Rafee Kamouna.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-16355937794284328532014-03-10T23:04:06.425-04:002014-03-10T23:04:06.425-04:00Well, since you are all expressing it in terms of ...Well, since you are all expressing it in terms of odds and possibilities, what do the bookies in London say? What odds are they giving?Unknownhttps://www.blogger.com/profile/02955547844743166800noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79925499637858758732014-03-10T19:50:23.930-04:002014-03-10T19:50:23.930-04:00I agree with Dom. Having taken Lipton's course...I agree with Dom. Having taken Lipton's course, I remember him saying that "for the right odds" he would be willing to bet that P=NP... that's a far cry from thinking that P=NP. One concrete thing he said was that it's debatable whether all the NP-complete problems should be considered independent problems or just versions of one problem. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-32563113223590710202014-03-10T12:45:04.360-04:002014-03-10T12:45:04.360-04:00Håstad, not Hastad.Håstad, not Hastad.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43729971564679740202014-03-10T11:41:56.654-04:002014-03-10T11:41:56.654-04:00"also not Dick Lipton (who seems to be who ev..."also not Dick Lipton (who seems to be who everyone points to) as a serious theorist who thinks P=NP" - while I'm not sure this sentence makes sense grammatically, I would also argue its truth. IMHO Lipton thinks P=NP is possible, which is not the same as thinking P=NP. I also think that P=NP is possible but if I had to guess, I would guess there are not equal.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com