Hacker News Reader

Comment by joe_the_user | Hacker News Reader

Working programmers and even people concerned with producing useful algorithm probably shouldn't care about P=NP?. It seems very likely to be true and if it isn't true, it seems like a polynomial algorithm would be unwieldy indeed. Further, P!=NP is a theory entirely about worst case scenarios. Many NP complete problems are actually quite solvable in the average case and the worst case can have little relation to the average case (SAT solvers that are quite fast on average exist now, for example).

For logicians and mathematicians, a proof of N=NP? would be an incredible accomplishment simply because it's a problem that at this point no one know where to start on and so by definition, the proof would be a piece of remarkable and surprising mathematics giving people much to think on.

View on HN

P=NP is very likely to be true? I would say it's very likely to be false.

Why do I say that? Because it's possible to construct, say, SAT3 problems such that it seems impossible to solve them in polynomial time. If some problems can't be solved in polynomial time, then P!=NP.

Why do you think that it's "very likely" that P=NP?

Given the next sentence (...if it isn't true, it seems like a polynomial algorithm would be unwieldy indeed), I think the GP actually meant P!=NP to be true.

SAT solvers are not fast on average. Even some very simple random distributions produce small (<100 variables) SAT instances that are very hard for the solvers.

Do you have a link ? I've been on the lookout for small hard SAT instances for some time and haven't really found any.

SAT competition 2018 http://sat2018.forsyte.tuwien.ac.at/index.php had a track with random instances. The article "Generating the Uniform Random Benchmarks" in https://helda.helsinki.fi/bitstream/handle/10138/237063/sc20... contains the descriptions of the random instances used.

Thanks for the link, but it seems difficult to answer the question "find a SAT instance with no more than 100 variables which all competing solvers failed to solve in the allowed time" from the information presented here.

I'm going to download the benchmarks and try to correlate them with the results CSV table (which doesn't show number of variables for each instance), but since the full random benchmarks are 2.9 GB compressed this might take a fair amount of work.

If you can provide any further guidance on finding the relevant instances I'd appreciate it.

Also note that just specifying the number of variables may not be terribly informative if you don't also specify the maximum clause size and the number of clauses.

For example I see some instances here with 120 variables but they are 7-SAT with around 10k clauses. Unless I'm mistaken reducing those to <=3-SAT will require adding about 20k more variables and tripling the number of clauses.

Reply on news.ycombinator.com