Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

romvf.wordpress.com

Post reply on HN
Print view View original

101–110 of 156 posts

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

#101

Post by natep »

jchonphoenix wrote: post #52
moultano wrote: post #10

Earlier quoted context omitted.

That's incorrect unless I'm misreading you. 3 SAT is NP-complete, which means that if this algorithm's polynomial performance holds up, you can generalize it to solve any problem in NP in poly time.

Just to be nitpicky, 3 SAT is NP-Complete which means its NP-hard. The NP-hard property allows you to reduce any problem in NP to it. As you stated it, generalizing (or reducing) 3-SAT to another problem proves nothing and is a common mistake for undergraduates learning complexity theory (reducing the wrong way).

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'

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

#102

Post by anorwell »

dejb wrote: post #93
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.

The point I was trying to make (badly) was that the actual claim doesn't imply P = NP, only that P = NP-complete. Given that factoring isn't known to be NP-complete (or co-NP-complete) this paper doesn't imply that factoring is in P.

If a single NP-Complete problem is in P, then P=NP. This is what NP-Complete means. In particular, factoring would be in P. Conversely, factoring is not NP-complete, so if factoring were in P, we could not draw any conclusions about P=?NP.

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

#103

Post by kd0amg »

dejb wrote: post #98
cperciva wrote: post #62

Earlier quoted context omitted.

Factoring is in NP. Proving that P=NP would, by definition, imply that large numbers can be factored in polynomial time. The issue of whether it's a feasible amount of work is exactly what I was addressing.

True. However I don't think the article really implies that P = NP (although the title certainly does). From what I can see the article only addresses the class of NP-complete problems. Factoring is not known or believed to be NP-complete so it wouldn't directly prove that factoring was in P. Please correct me if I'm wrong. Edit : For some reason I can't reply to posts so I'll do it here. RiderOfGiraffes> It would wi…

The NP-complete problems are a subset of NP ("nondeterministic polynomial") problems, specifically those to which all NP problems are polynomial-time reducible. They are, in essence, the hardest problems in class NP. It's pretty trivial to show that integer factoring is in NP; what's not known is whether it's NP-complete. If any NP-complete problem is in P, then via polynomial-time reduction, all problems in NP are in P.

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

#104

Post by JadeNB »

bdr wrote: post #86
dejb wrote: post #82

Earlier quoted context omitted.

Speaking pedantically, P is in NP also. I suspect that NP is being used as shorthand for NP-complete, not just NP. As for actual deterministic factorization Wikipedia says that 'It is suspected to be outside of all three of the complexity classes P, NP-complete, and co-NP-complete' So even if this showed 'P = NP-complete' it may not imply imply factorization is in P. I'm at the limits of my rusty complexity knowledge…

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 …”.

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

#105

Post by tomjen3 »

vilda wrote: post #58
azakai wrote: post #17

Earlier quoted context omitted.

It is almost certainly not correct, simply because so many have tried, and none succeeded. However, this guy seems very cool - he is humble about his work, appears very serious, and even puts his code on github. And even if wrong, his approach might be interesting.

"because so many have tried, and none succeeded" Words worth of a politician, but not a hacker!

No words worthy of a Hacker - we are bound by reality.

Politicians are not.

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

#106

Post by RiderOfGiraffes »

dejb wrote: post #98
cperciva wrote: post #62

Earlier quoted context omitted.

Factoring is in NP. Proving that P=NP would, by definition, imply that large numbers can be factored in polynomial time. The issue of whether it's a feasible amount of work is exactly what I was addressing.

True. However I don't think the article really implies that P = NP (although the title certainly does). From what I can see the article only addresses the class of NP-complete problems. Factoring is not known or believed to be NP-complete so it wouldn't directly prove that factoring was in P. Please correct me if I'm wrong. Edit : For some reason I can't reply to posts so I'll do it here. RiderOfGiraffes> It would wi…

I believe you to be mistaken. Let me explain.

Proving that any single NPC problem is in P will be enough to prove that every NP problem is in P, and not just the NPC ones. Suppose A is is NP, B is in NPC, and further suppose that solving B is polynomial. Reduce A to B (a polynomial operation because B is in NPC), solve B (a polynomial operation by assumption), and convert the solution back to a solution of A (a polynomial operation because B is in NPC), and that gives a polynomial solution of A.

Proving that any single NPC problem is not in P is enough to prove that all NPC problems are not in P. It would will leave in question those problems in NP, but not NPC. Currently it is generally believed, but not known, that factoring is such a problem.

Added in edit, to reply to your edit:

    RoG> It would will leave in question those problems
    RoG> in NP, but not NPC. Currently it is generally 
    RoG> believed, but not known, that factoring is such
    RoG> a problem.

    dejb> This is exactly my point. P = NPC doesn't imply
    dejb> anything about factorisation. Since factorisation
    dejb> is in NP we haven't shown that P = NP
Read my entire comment again. In particular, the second paragraph. In particular:

    Proving that any single NPC problem is in P will be
    enough to prove that every NP problem is in P.
More specifically, proving 3-SAT is in P will prove that every NP problem, not just the NPC problems, but every NP problem, is in P. Including factoring.

Let me add a little more.

   1. Suppose 3-SAT is in P.
   2. Let A be any problem in NP.
   3. 3-SAT is in NPC.
   4. Therefore A can be converted to A', an instance of 3-SAT.
   5. By (1), A', as an instance of 3-SAT, can be solved in polynomial time
   6. Hence A has been solved in polynomial time.
Replace "A" with factoring, and thus we've shown that P=NPC implies that factorisation is in P.

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

#107

Post by RiderOfGiraffes »

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

The key lies in generating hard instances. As cperciva has said in http://news.ycombinator.com/item?id=2121837 - most instances of most NPC problems are "easy."

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

#108

Post by patio11 »

cperciva wrote: post #62
tshaddox wrote: post #45

Earlier quoted context omitted.

To pick on a small part of your comment: Do any theoretical computer scientists seriously worry that a proof that P=NP would threaten cryptography? It's not like a proof would suddenly make an i7 able to factor huge numbers in polynomial time. Also, while all polynomial-time algorithms are considered "tractable" in theoretical CS, that doesn't mean that they're all practical on current hardware (nor does it claim to…

Factoring is in NP. Proving that P=NP would, by definition, imply that large numbers can be factored in polynomial time. The issue of whether it's a feasible amount of work is exactly what I was addressing.

The issue of whether it's a feasible amount of work is exactly what I was addressing.

One of the reasons this would be a huge result is that even a very expensive polynomial-time solution for any NP-complete problem (say, one which is O(n^2000) and would take several billion years to run against a 256-bit key) is only going to get faster over time. Also, the experience of cryptography is that once cracks start appearing in an algorithm the mathematicians start trying to wedge their chisels in and hammer those cracks into fractures, into holes, and eventually into whatever you call something which no longer resembles a crack so much it resembles absence-of-wall.

There are specific mechanisms by which this would happen, too. A near miss on P=NP would mean funding for professors looking into refining it, and professional interest generally, would suddenly explode. Nobody wants to fund or work on duds, but big contributions to this problem would make careers.

Not incidentally, while the government funds quite a bit of academic research, this particular branch of mathematics is of special interest to one type of government customer which has ways of getting funding for projects expedited if they are in the national interest... and it is virtually inconceivable that they would not find very, very strong national interest in the vicinity of this result.

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

#109

Post by jchonphoenix »

natep wrote: post #101
jchonphoenix wrote: post #52

Earlier quoted context omitted.

Just to be nitpicky, 3 SAT is NP-Complete which means its NP-hard. The NP-hard property allows you to reduce any problem in NP to it. As you stated it, generalizing (or reducing) 3-SAT to another problem proves nothing and is a common mistake for undergraduates learning complexity theory (reducing the wrong way).

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.

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

#110

Post by bdr »

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 …”.

Yep. I should just stop posting today. :)
Post reply on HN