The polynomial algorithm for 3-SAT problem (or P=NP)

Post by praptak » Thu, Jan 20, 2011, 10:52 AM UTC

mitko wrote: post #72

xtacy wrote: post #47

Earlier quoted context omitted.

I would like to clarify that just because an algorithm runs slower than the ones used by solvers in competitions like SAT, it doesn't mean much, as we're looking at asymptotic complexity here. To give an example: the "PRIMES is in P" paper gives a poly time algorithm to determine if a given number is prime or not, but in practice, it runs slower than tests like probabilistic algorithms like Miller-Rabin.

Another example is Linear Programming - it is provably polynomial using the ellipsoid algorithm but people tend to use algorithms (such as simplex) which are not provably in P but run much faster in practice.

Post by wnoise » Thu, Jan 20, 2011, 11:23 AM UTC

RiderOfGiraffes wrote: post #126

wnoise wrote: post #121

Earlier quoted context omitted.

Which randomness models in particular? The two Erdős–Rényi models G(n,p) vs G(n, M)? I thought for almost all purposes they gave the same answer as long as equivalent M and p were chosen in the large n limit, because the concentration around M will be so tight due to the law of large numbers. Is there some other model you're looking at? Random without qualification is used to mean "uniformly". For this specific case…

My sense is that there are hard 3-coloring problems in graphs that don't look "random". Certainly the ones I generate have a small number of vertices with very high degree, and the others are more reasonable. This is why I say that there are potentially things happening with different random models. But you are certainly right on all counts. However, where you say this: .... it's been given "physicist proofs". There'…

Post by wlievens » Thu, Jan 20, 2011, 11:58 AM UTC

sid0 wrote: post #120

wlievens wrote: post #117

Earlier quoted context omitted.

Here's how I intuit this: 3-SAT is like "machine language" for other NP problems. Any other NP problem can be "compiled down" to 3-SAT statements. Though it's probably inaccurate, that's how I intuit the matter.

Though it's probably inaccurate, that's how I intuit the matter. It's actually quite accurate, but you can do even better: any other NP problem can be "compiled down" to one 3-SAT statement.

Post by khafra » Thu, Jan 20, 2011, 1:52 PM UTC

bravura wrote: post #59

leelin wrote: post #48

Where is the market among the HN community on betting this proof is correct (or the market for P=NP in general)? My bid/ask is 0% / 0.02% I think I'd wager at most a 1% chance that P = NP, and, I'll be generous and put the odds that this particular person cracked it first at 2% of 1% (I know he has code posted, but think of all the smart people who failed, and within my 1% is the case where P=NP but no human ever pro…

http://www.longbets.org/ is a market for long bets, e.g. “Over a ten-year period commencing on January 1, 2008, and ending on December 31, 2017, the S & P 500 will outperform a portfolio of funds of hedge funds, when performance is measured on a basis net of fees, costs and expenses.” PREDICTOR: Warren Buffett CHALLENGER: Protege Partners, LLC

Post by natep » Thu, Jan 20, 2011, 2:42 PM UTC

jchonphoenix wrote: post #109

natep wrote: post #101

Earlier quoted context omitted.

He said generalize it (the algorithm) to other NP problems, which I took to mean 'turn every NP problem into 3-SAT and solve that'

The word generalize is meaningless and undefined, which is what led to your confusion as well as multiple interpretations (which is one of the things I was picking at). To say you generalize an NP problem isn't even a statement that typechecks in the language of complexity. Reduction on the other hand, is a formally defined term and is very specific in what it means exactly.