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

51–60 of 156 posts

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

#51

Post by caf »

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…

I believe Intrade are open to suggestions for new markets (they have "Scientific" category where this would fit).

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

#52

Post by jchonphoenix »

moultano wrote: post #10
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"

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

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

#53

Post by jchonphoenix »

tshaddox wrote: post #45
cperciva wrote: post #20

I'm not at all an expert on this material, but some random points to get people started: 0. This guy looks orders of magnitude less looney than the usual P=NP prover. I hope someone who knows this material well steps in soon. 1. This guy has implemented his algorithm. This is a very good sign -- most garbage "algorithms" are exposed to be broken when people try to implement them. 2. Most 3SAT problems are "easy". Bei…

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…

Actually, yes. Normally, when something is placed firmly in P, improvements are quickly made and a spur of research firmly lowers the bounds of the algorithm.

Additionally, P=NP suggests that NP in RP. If an inefficient deterministic algorithm in P is found, I'm sure a much faster randomized algorithm would soon follow.

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

#54

Post by jrockway »

stevejohnson wrote: post #36
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.

"Instantaneously, for free" is nowhere near what this paper claims (O(n^4m)).

But P is good and NP is bad, and fast is good and slow is bad, so P must be fast!

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

#55

Post by vilda »

slashcom wrote: post #28

Zero other (english) publications by the author in the Cornell archive and only four references within. Not an indicator as to whether the paper is correct (I haven't read it), but that's "smelly".

Not really. There are many great researchers publishing in their language only. Especially in countries where research is not heavily funded. For some, 800EUR for a conference is just too much.

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

#56

Post by spicyj »

jchonphoenix wrote: post #46
equark wrote: post #18

I know nothing about N=NP debate, but does the claim P=NP and the existence of a published algorithm ( https://github.com/anjlab/sat3 ) make this claim easier to verify than the claim P!=NP. Isn't the point that P=NP has great practical significance that will be immediately recognized?

You'd be surprised. Sometimes its much harder to find hidden faulty logic in a proof for an algorithm's correctness or running time. If I recall correctly, Ramanujan once wrote a proof for 1=2 that baffled mathematicians for quite some time before they figured out what was wrong. I believe that proof was rather short (< 1 page). For a long proof with a tiny error, things could be much worse.

Can you find a reference for Ramanujan's "proof"? I looked briefly and can't find one, but I'd be very interested to see what the proof was.

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

#57

Post by tanis »

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.

Very true, I'm sorry if I implied otherwise above. However, using a well-known SAT benchmark to assess correctness/performance in the absence of a clearer statement of the algorithm would still be a good step to take, if someone was interested.

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

#58

Post by vilda »

azakai wrote: post #17
jey wrote: post #2

Why do we think this is worthy of voting up? Is there any reason to think it might be correct?

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!

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

#59

Post by bravura »

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

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

#60

Post by jongraehl »

jey wrote: post #13
jackfoxy wrote: post #3

OK, I just upvoted purely for the reason of keeping it on the front page a little longer so someone more qualified has a chance to glance at this. Without any evidence and no qualification to judge myself, it seems highly unlikely.

The prior probability of it being correct is so low that we should be flagging it, not upvoting it. There's many, many false "proofs" of P=?NP out there. If I write a paper formatted in LaTeX saying that I cloned a T-Rex in my backyard, should it be upvoted so that an expert in cloning can take a look at it?

To be concrete, an average nicely formatted P=NP proof claim is correct with probability less than 10^(-5) (IMO).
Post reply on HN