Predicting When P=NP Is Resolved

Post by tgflynn » Mon, Dec 23, 2019, 12:30 AM UTC

Laakeri wrote: post #28

joe_the_user wrote: post #18

Earlier quoted context omitted.

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…

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.

Post by empath75 » Mon, Dec 23, 2019, 1:17 AM UTC

hinkley wrote: post #25

jacobkg wrote: post #15

In my mind I always regard P/NP in the same category as the Riemann Hypothesis^. That has been open since 1859 (160 years) and shows no signs of cracking. So in other words we may be in for a long wait. ^Perhaps because one of the hypothesized examples of a hard problem is the factoring of multiples of large primes (though not proved NP Complete). Or perhaps because they are both extremely famous open problems.

One of the things that slows scientific progress is the lack of cross-discipline learning. Every so often you hear about someone taking an old concept from another field and applying it. Quite a few breakout companies have combined interdisciplinary knowledge into one product and made a mint. So many people are affected by NP complete problems that you'd think that someone would have a problem that appeared simpler o…

Post by marcosdumay » Mon, Dec 23, 2019, 2:33 AM UTC

ookdatnog wrote: post #29

marcosdumay wrote: post #12

Earlier quoted context omitted.

Since an algorithm for running NP-complete problems in P-time would be enough to prove whether P=NP, wouldn't the impossibility to prove it just prove that P!=NP?

Surprisingly, a theorem being unprovable does not mean that the theorem is untrue, even if you can prove its unprovability! This was shown by Goedel ( https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... ). He showed that there exists no system powerful enough to express theorems about the natural numbers which can prove all facts about natural numbers and be sound (ie not prove things that are untrue).

Post by saagarjha » Mon, Dec 23, 2019, 2:58 AM UTC

lonelappde wrote: post #36

someguy12342 wrote: post #23

Earlier quoted context omitted.

I think RJ Lipton (blog author) and Knuth believe it could be true. However, most complexity theorists don't (I think Fortnow does a survey of theorists on this every few years). Knuth says something like "well all it would take is a single algorithm for any of these hundreds of problems". A fine take for the godfather of algorithms. At the same time, there are many people who have in some sense tried to find such an…

http://www.informit.com/articles/article.aspx?p=2213858&WT.m... Note that Knuth does not believe that the constant factor on the P algorithm be will be less than the size of the entire Universe.

Post by lonelappde » Mon, Dec 23, 2019, 4:00 AM UTC

marcosdumay wrote: post #35

ookdatnog wrote: post #29

Earlier quoted context omitted.

Surprisingly, a theorem being unprovable does not mean that the theorem is untrue, even if you can prove its unprovability! This was shown by Goedel ( https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_... ). He showed that there exists no system powerful enough to express theorems about the natural numbers which can prove all facts about natural numbers and be sound (ie not prove things that are untrue).

That's not exactly what I'm saying. What I am saying is that it's impossible for it to be true and unprovable. If it is true, it means a proof exists. Also, I am talking about this specific problem.