lol
sorry guys. this site is not worth taking seriously anymore
The polynomial algorithm for 3-SAT problem (or P=NP)
61–70 of 156 posts
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#62I'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…
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.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#63Earlier 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)
One time pads are not useful in many cases, but they have been used:
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#64Just this months there's another paper on arXive that uses 3-SAT to proove P!=NP http://arxiv.org/abs/1101.2018 A list of articles published on the P=NP debate is here http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Looks like someone thinks they've solved the problem every month or so :)
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 :)
I completely disagree - think of all the useful np problems that we'd be able to solve in the large scale.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#65I'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…
>Do any theoretical computer scientists seriously worry that a proof that P=NP would threaten cryptography?
Yeah, that's how crypto works as a field. As soon as there's a shadow of a doubt that something is secure in even the least likely edge case, it gets tossed out. MD5 was basically considered dead once someone showed to how create a collision with (correct me if I'm wrong) two very long, very unlikely, very similar (?) plaintexts. It didn't threaten anyone's actual use of MD5 in an immediate sense, but MD5 was shown not to be reliable and in the crypto world an algorithm's reliability is sort of treated as binary.
(I apologize to the true security folk in the crowd if I've oversimplified something here.)
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#66Earlier quoted context omitted.
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.
Just parallelize your algorithm and use n^5 machines ;)
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#67Earlier quoted context omitted.
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.
I was able to find this, though it's just some algebra tricks rather than a professional mathematician's musings:
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#68I 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"
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!
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#69Just this months there's another paper on arXive that uses 3-SAT to proove P!=NP http://arxiv.org/abs/1101.2018 A list of articles published on the P=NP debate is here http://www.win.tue.nl/~gwoegi/P-versus-NP.htm Looks like someone thinks they've solved the problem every month or so :)
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 :)
The negative effects of ruining public-key cryptography completely pale in comparison to the benefits. The traveling salesman problem alone has so many practical and scientific applications that it would be worthwhile, and that's not even counting subgraph isomorphism or knapsack.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#70I'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…
Colin, no offense, and you are certainly a good coder & cryptographer, but that doesn't make know about everything in mathematics.