3 ms·
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 d
by 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 agoMy 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.