The polynomial algorithm for 3-SAT problem (or P=NP) • Hacker News Board

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

#121

Post by wnoise » Thu, Jan 20, 2011, 9:12 AM UTC

RiderOfGiraffes wrote: post #118

wnoise wrote: post #113

Earlier quoted context omitted.

It's actually pretty easy to construct hard problems. A random 3-SAT problem is hard when it has the right density ratio of clauses to Boolean variables. Too few, and it's (relatively) easy to find a satisfying assignment. Too many, and it's easy to find a contradiction. This ratio is around 4.26, and it can actually be viewed as "thermodynamic" phase transition. In the large n limit, almost all 3-sat problems with a…

I'd be interested to see a reference for that result. I've been working for some time on the equivalent problem for graph 3-coloring, and really there are only some vague, heuristic results. I should think it also depends on the randomness model you use. In graph coloring some random processes give easy problems and others give hard problems for the same density.

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 (3-SAT), there are only four reasonable readings: both (variables within a clause), and (clauses within the set of all possible clauses) can be chosen with or without replacement. Neither makes a difference in the large n limit.

http://books.google.com/books?id=zyktZTqZSzMC&lpg=PA414&...

is from a reasonable book.

It's true that this phenomenon hasn't been completely rigorously proven, but it's been given "physicist proofs". There's enough evidence that it's unreasonable to not consider it true.

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

#122

Post by roel_v » Thu, Jan 20, 2011, 9:26 AM UTC

jey wrote: post #8

monochromatic wrote: post #4

Earlier quoted context omitted.

It's on the arXive, so you know it's legit.

Sarcasm, right? The arXiv has very little quality control (intentionally).

I think the point was that quite a bit of what is on arXiv is from quacks and nutcases. (maybe not the majority, or even a large part - but enough to cast some shadow over arXiv itself, and therefore over other submissions as well).

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

#123

Post by EGreg » Thu, Jan 20, 2011, 9:27 AM UTC

Could it be ... P = NP? Most people suspected otherwise.

Someone should really verify his algorithm on various SAT sets. But I have to say that his approach is very good and humble... he suggests he may have solved the problem -- but it is up to us to verify! I'd like to follow this further, so I bookmarked it via an upvote.

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

#124

Post by tybris » Thu, Jan 20, 2011, 9:33 AM UTC

Right, he just didn't want to submit it to a peer-reviewed journal?

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

#125

Post by CJefferson » Thu, Jan 20, 2011, 9:39 AM UTC

Having read this paper (and being reasonably knowledgeable on the subject), I'm convinced this paper is wrong, or at least very underexplained.

The algorithm uses an algorithm similar to the well-known '3-consistency', which has been shown to solve quite a lot of classes of problems, in particular some that are solved very poorly by the normal learning-based systems used in most SAT solvers.

The paper aims to strengthen 3-consistency slightly, using permutations. However, while that is a reasonable strategy, it is entirely unclear to me, and unclear in the paper, while that gives poly-time solving time.

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

#126

Post by RiderOfGiraffes » Thu, Jan 20, 2011, 9:44 AM UTC

wnoise wrote: post #121

RiderOfGiraffes wrote: post #118

Earlier quoted context omitted.

I'd be interested to see a reference for that result. I've been working for some time on the equivalent problem for graph 3-coloring, and really there are only some vague, heuristic results. I should think it also depends on the randomness model you use. In graph coloring some random processes give easy problems and others give hard problems for the same density.

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's enough
    evidence that it's unreasonable to not consider it true.

There had been a lot of evidence around for quite some time that primality was harder than P (assuming P!=NP), and yet it turns out to be in P, even without PvsNP being settled. I'm suspicious. I still believe that hard instances can be found, and that "most" of them will look as you describe, random-ish with the right parameters, but I'm wary about claiming that most things that look like that will, in turn, be "hard."

But I suspect we're in agreement, possibly "violent agreement."

ADDED In EDIT: Forgot to say, thanks for the reference.

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

#127

Post by JoeCamel » Thu, Jan 20, 2011, 10:17 AM UTC

JadeNB wrote: post #104

bdr wrote: post #86

Earlier quoted context omitted.

Actually, cperciva is right here. Factoring is in NP, therefore if P=NP then there is a polynomial-time algorithm for factoring. Many problems harder than NP are NP-complete, so saying factoring is in NP-complete would not imply the conclusion. Also, there are problems in NP that are neither in P, nor are they NP- or co-NP-complete.

> Also, there are problems in NP that are neither in P, nor are they NP- or co-NP-complete. Err, it seems to me you've got a very serious statement there. I think you mean “that are not known to be …”.

No, there actually are problems in "NP-intermediate" class (if P!=NP) although they are artificial. :) And, of course you are right, for many other problems researchers suspect they might be in NPI. See http://cstheory.stackexchange.com/questions/79/problems-betw...

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

#128

Post by A1kmm » Thu, Jan 20, 2011, 10:26 AM UTC

Is anyone else struggling to understand theorem 2 on pages 15-16?

It sounds like what they are saying is equivalent to the following: If S1 intersect S2 has a solution, and S1 intersect S3 has a solution, then the system S1 intersect S2 intersect S3 has a solution.

But this is evidently false. Consider the case where the CTS included each of the following rows, and were empty everywhere else (after re-ordering the columns so the same-name columns were in the same final column):

  (1) 000 
  (2)  001
  (3) 0 00

In this case, (1) and (2) are consistent, and (1) and (3) are consistent, but (2) and (3) are inconsistent.

I suspect the problem they set up the induction for might not perfectly align with the theorem, but it needs more careful examination.

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

#129

Post by larelli » Thu, Jan 20, 2011, 10:32 AM UTC

RiderOfGiraffes wrote: post #107

What we should do is generate a class of instances of 3-SAT that are expected to be hard, and then try the solver on them and see what the runtime looks like as a function of the size of the input. Recently someone claimed a polynomial-time graph coloring algorithm. I generated hard instances, their "solver" blew up. Claim debunked. It should be simple enough to do the same for this (for some definition of simple). T…

I tried running the code on Pigeon Hole Problems, but it crashed. :(

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

#130

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

xtacy wrote: post #47

tanis wrote: post #38

I've read the paper fairly closely, and it mostly seems like the author is hiding a conflict-driven search in ill-stated data structures, which allow him to perform a faulty analysis of the runtime of his algorithm. I've implemented a SAT solver and read the literature extensively. This paper is not up the standards of clarity imposed by that literature, see, eg, "Efficient Conflict Driven Learning in a Boolean Satis…

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.

"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."

I agree in principle, but the example is a bad one. Here, a deterministic polynomial time algorithm is stacked against probabilistic polynomial time algorithms.

In SAT, we'd have the (hypothetically) polynomial algorithm against exponential time algorithms. Theoretically, the constants in the polynomial might of course be so large as to erase the advantage on non-galactic problem sizes but this happens rarely.