4 ms·

Relevant blog post by an actual complexity theorist: https://blog.computationalcomplexity.org/2018/10/if-pnp-then-we-have-alg-for-sat.html https://blog.computat

Relevant blog post by an actual complexity theorist: https://blog.computationalcomplexity.org/2018/10/if-pnp-then-we-have-alg-for-sat.html https://blog.computationalcomplexity.org/2018/10/if-pnp-then.... >The following does not quite show it can't happen but it does give one pause: an old result of Levin's shows that there is a program you could write NOW such that if P=NP then this program decides SAT except for a finite number of formulas (all of which are NOT in SAT) and can be proven to work in poly time (I will later give three pointers to proofs). The finite number of formulas is why the people above may still be right. But only a finite number- seems like a weak kind of nonconstructive. So, based on this post, it is actually not known that P=NP implies existence of polynomial time algorithm for deciding SAT. The universal search idea only yields a polynomial time algorithm that decides SAT for all but a finite number of formulas.

CaptainNegative 3y ago
I didn't say it solves every SAT problem in polynomial time, I said it can > find satisfying assignments to satisfiable SAT instances in polynomial time The distinction between this and solving SAT, and the slight strengthenings one can make to universal search, are part of those few technicalities I promised to gloss over. Also, cut the snark. I'm not a complexity theorist, but my PhD thesis was in the intersection of graph algorithms and complexity (the first word of the title literally being "Hardness"), and I'm more than qualified enough to understand and present well-known complexity results from half a century ago, even when a misguided appeal to authority is at play.
- alex_smart 3y ago
  My comment was not meant to be snarky. I actually got the (incorrect) impression from reading your comment that P = NP would imply a polynomial time algorithm that decides SAT. I decided to look up a more authentic source and shared the best resource that I could find. I am guessing you took offense at the "an actual complexity theorist" part of my comment, but it wasn't a personal remark against you. The general audience of hackernews is programmers and startup enthusiasts. >I'm more than qualified enough to understand and present well-known complexity results from half a century ago, even when a misguided appeal to authority is at play. All the more reason you should not be so insecure and automatically assume the worst about other people's intentions. * * This time the snark is intentional.

CaptainNegative 3y ago

I didn't say it solves every SAT problem in polynomial time, I said it can > find satisfying assignments to satisfiable SAT instances in polynomial time The distinction between this and solving SAT, and the slight strengthenings one can make to universal search, are part of those few technicalities I promised to gloss over. Also, cut the snark. I'm not a complexity theorist, but my PhD thesis was in the intersection of graph algorithms and complexity (the first word of the title literally being "Hardness"), and I'm more than qualified enough to understand and present well-known complexity results from half a century ago, even when a misguided appeal to authority is at play.

alex_smart 3y ago
My comment was not meant to be snarky. I actually got the (incorrect) impression from reading your comment that P = NP would imply a polynomial time algorithm that decides SAT. I decided to look up a more authentic source and shared the best resource that I could find. I am guessing you took offense at the "an actual complexity theorist" part of my comment, but it wasn't a personal remark against you. The general audience of hackernews is programmers and startup enthusiasts. >I'm more than qualified enough to understand and present well-known complexity results from half a century ago, even when a misguided appeal to authority is at play. All the more reason you should not be so insecure and automatically assume the worst about other people's intentions. * * This time the snark is intentional.