tag:blogger.com,1999:blog-3722233.post5685671021929077438..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: P = NP Need Not Give a SAT AlgorithmLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-26521844747498461582019-01-02T09:06:20.463-06:002019-01-02T09:06:20.463-06:00You need that statement provable in PA, otherwise ...You need that statement provable in PA, otherwise the argument doesn't work I think.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-20207784282986760112018-11-22T17:40:46.800-06:002018-11-22T17:40:46.800-06:00This is somewhat off topic, but if P=NP would that...This is somewhat off topic, but if P=NP would that mean that even though cryptography would be very limited, we could still have really good steganography? If P=NP, then machine learning could build very good models of cover texts (i.e. color images, video) that are presumably NP-hard. Does it follow that we could build stego systems that are secure against steganalysis?Anonymoushttps://www.blogger.com/profile/03281901712454837586noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45195559446122069662018-11-03T02:16:09.566-05:002018-11-03T02:16:09.566-05:00Also note that any proof that a fixed algorithm ca...Also note that any proof that a fixed algorithm can compute all of SAT correctly if P = NP, would imply that P != NP, if true, would be provable in Peano Arithmetic... Bjørn Kjos-Hanssenhttps://www.blogger.com/profile/09050965655510102773noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37344775699035806662018-11-02T16:14:40.182-05:002018-11-02T16:14:40.182-05:00I've posed this somewhat related question: htt...I've posed this somewhat related question: https://cstheory.stackexchange.com/questions/41832/is-there-an-algorithm-that-finds-the-forbidden-minorsdomhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34432895269953513032018-11-02T14:08:14.827-05:002018-11-02T14:08:14.827-05:00Yate! ( ... yet another trivial error :-)Yate! ( ... yet another trivial error :-)Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-84487335822430175122018-11-02T08:42:54.790-05:002018-11-02T08:42:54.790-05:00Not quite. Consider the following statement (true ...Not quite. Consider the following statement (true by Levin's construction). There is an algorithm A such that<br />Factoring is in P -> A in polytime and A solves factoring<br /><br />As above you have<br />Factoring not in P OR A in polytime and A solves factoring<br />and<br />A in polytime and A solves factoring -> Factoring is in P<br /><br />But this most certainly does not settle whether factoring is in P.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-87726011704757651852018-11-02T07:19:15.750-05:002018-11-02T07:19:15.750-05:00In a comment to Bill's post I said that provin...In a comment to Bill's post I said that proving that for a particular A<br /><br />P=NP -> (polytime (A) AND A=SAT)<br /><br />Is (logically) equivalent to<br /><br />P <>NP OR (polytime (A) AND A=SAT)<br /><br />But polytime (A) AND A=SAT implies P=NP<br /><br />So proving the above implication is equivalent to solve P=?NP (and clearly such a proof cannot relativize). Is it correct?Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-2262377950852674052018-11-01T17:38:05.863-05:002018-11-01T17:38:05.863-05:00OK, after the update of the claim to SAT^A I can u...OK, after the update of the claim to SAT^A I can understand.domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-7874507699976305742018-11-01T15:38:22.147-05:002018-11-01T15:38:22.147-05:00Thanks. Fixed the typo.Thanks. Fixed the typo.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-26621502554502750142018-11-01T15:36:33.907-05:002018-11-01T15:36:33.907-05:00Nice!!!
Typo in the theorem definition? "......Nice!!!<br /><br />Typo in the theorem definition? "... does not compute ***SAT^A*** correctly on all inputs "Marzio De Biasihttps://www.blogger.com/profile/18441670787376943932noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-78413667432040056722018-11-01T11:32:06.299-05:002018-11-01T11:32:06.299-05:00It's an order of quantifiers. If P^A = NP^A th...It's an order of quantifiers. If P^A = NP^A there is an polytime M such that L(M^A) = SAT^A, but my proof shows that M has to depend on A. <br /><br />I don't see any circularity in the definitions. I'll leave it to Marzio to say how this proof connects with what he commented on Bill's post.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-48755027781443436482018-11-01T10:03:55.147-05:002018-11-01T10:03:55.147-05:00I don't get this Theorem. Wouldn't this im...I don't get this Theorem. Wouldn't this imply that there's no M that can compute SAT in polynomial time? (If M never queries the oracle.)<br /><br />In the proof, isn't the definition of \varphi_n and A circular?<br /><br />Finally, have you seen Marzio's comments to Bill's post?domhttps://www.blogger.com/profile/05790539025733385232noreply@blogger.com