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

41–50 of 156 posts

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

#41

Post by ot »

Peaker wrote: post #26
ot wrote: post #22

Earlier quoted context omitted.

And as always, we'd better hope that the proof is wrong. P=NP would (almost) imply the impossibility of cryptography, but even more seriously a lot of brainpower from the top theoretical computer scientists (whose proofs often begin with "suppose that P != NP...") would have been wasted :)

P=NP does not imply cryptography is impossible at all. For example, "Quantum encryption" allows you to send data and know whether you're being eavesdropped. Then, once you manage to send it without being eavesdropped, you can use what you sent as a one-time-pad safely. You could of course regress to distributing one time pads to everyone :-) Also, if P = NP, there are still NP hard and Exp problems that remain outsid…

That's why I said "almost" :) AFAIK, cryptography without P != NP is an open question.

BTW, quantum encryption is not encryption as we know it (a purely functional deterministic bijective transformation of the message), as it requires special hardware, optical fibers, etc...

As of EXP etc... I am not aware of any (theoretical) encryption schemes that use problems harder than NP (actually most use circuit complexity, so NP/poly, but it is related). In designing encryption you often want polynomial verifiability (for decryption), and that implies NP membership.

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

#42

Post by jbri »

ot wrote: post #39
socketpuppet wrote: post #32

Earlier quoted context omitted.

How so? 1) One time pads are provably secure albeit impractical 2) Integer factorization is BQP, but not necessarily NP-complete.

1) One time pads require a secure channel to transmit the key, which must be the same length of the message. It is not a feasible cryptography scheme, more of a theoretical framework. 2) Integer factorization is trivially in NP (the decision problem "n has a factor < x" has a certificate: the factor)

A quantum channel provides protection against eavesdropping for random data, but does not provide security for specific data. A shared quantum channel can be used to easily produce a shared one-time key that only the two parties involved know, which can then be used to encrypt specific data over an unsecured channel.

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

#45

Post by tshaddox »

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

I suppose a proof that P=NP would still technically threaten cryptography, because if you assume that computer hardware performance increases polynomially with time you must concede that any given crypto technique will become practical to break after some amount of time.

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

#46

Post by jchonphoenix »

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.

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

#47

Post by xtacy »

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.

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

#48

Post by leelin »

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 proves it). Would anyone offer better odds than 1 in 5,000, or make a bid?

My knowledge is limited to taking Sipser's intro class in school; but as a programmer, I always find subset-sum to be the most tangible and convincing example that NP-hard feels pretty tough.

I love these announcements though; I am always humbled and fascinated by the resulting discussion.

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

#49

Post by ezalor »

dangrossman wrote: post #44
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.

Why would a polynomial time algorithm become instantaneous if you stick it behind an API?

The magic of the cloud! Imagine running that on Heroku (for instance): it would be costly (price) but possible.
Post reply on HN