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

91–100 of 156 posts

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

#91

Post by sonoffett »

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.

Cperciva is right, but I think you're mistaken when you say "many problems harder than NP are NP complete", NP complete problems are both NP and NP hard. NP hard is a class of problems such that every problem in NP can be reduced to any problem in NP hard. Meaning if P=NP then every problem in NP(including the NP complete problems) can be solved in polynomial time; all it takes is one algorithm that solves an NP complete problem in polynomial time (note that this does not show that P=NP hard, a much stronger claim).

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

#92

Post by bdr »

sonoffett wrote: post #91
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.

Cperciva is right, but I think you're mistaken when you say "many problems harder than NP are NP complete", NP complete problems are both NP and NP hard. NP hard is a class of problems such that every problem in NP can be reduced to any problem in NP hard. Meaning if P=NP then every problem in NP(including the NP complete problems) can be solved in polynomial time; all it takes is one algorithm that solves an NP comp…

You're right. I've got the brain hiccups.

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

#93

Post by dejb »

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.

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.

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

#94

Post by ezalor »

yhmv wrote: post #68
azakai wrote: post #14

Earlier quoted context omitted.

The existence of an algorithm to solve 3SAT in polynomial time is sufficient to prove P = NP, since 3SAT is NP-complete. That is, any NP problem can be reduced to solving 3SAT.

Coq could be used to reduce automatically, and more!

Seriously, Coq? What a name.

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

#95

Post by ezalor »

mitko wrote: post #75
dauphin wrote: post #40

Earlier quoted context omitted.

Yeah, and, seriously, a Russian?! Please...

Why not a Russian? For example the Russian Mathematics Olympiad is considered harder than the International Math Olympiad by many of the top contestants. Edit: why downvoting?

Perfume was illegal in USSR until 1986.

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

#97

Post by ezalor »

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.

Logic programming (Prolog, Rebol & co) is based on these kind of ideas.

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

#98

Post by dejb »

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.

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

This is exactly my point. P = NPC doesn't imply anything about factorisation. Since factorisation is in NP we haven't shown that P = NP

kd0amg> NP-complete problems ... are, in essence, the hardest problems in class NP.

From what I understand they a 'thought to be' the toughest but this isn't proven. If this article turned out to be true then they are reduced to being as hard as P. So who is still standing as a contender for the hardest problem in NP? - factorization of course as it has never been demonstrated to be polynomially reducible to NPC.

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

#99

Post by natep »

bdr wrote: post #80
bdr wrote: post #25

This is easy: just put your algorithm behind a web API. When I'm solving my NP-complete problems instantaneously, for free, I'll believe you.

Yeah this is dumb, should have read the OP.

Should have taken time to think. You don't even need to read the OP to know what you said is nonsense.

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

#100

Post by pekinb »

phamilton wrote: post #5

I don't think one example constitutes a conclusion. While demonstrating the nonexistance of an algorithm for 3-SAT problem would prove P!=NP, the existance of an algorithm merely means "Move along, let's try a different difficult algorithm"

I may be mistaken, and this might require an exhaustive search of the relevant literature, but I believe 3SAT is NP-Complete and therefore this one example does indeed lead to the stated conclusion.
Post reply on HN