Time to fire up Coq and really prove it.
My great grandchildren will be looking forward to the results :P
The polynomial algorithm for 3-SAT problem (or P=NP)
141–150 of 156 posts
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#142Earlier quoted context omitted.
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 polyn…
Can you supply a link to the proof that all NPC problems are equivalent? I remember learning it, but I can't remember how it worked.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#143Earlier quoted context omitted.
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 polyn…
Can you supply a link to the proof that all NPC problems are equivalent? I remember learning it, but I can't remember how it worked.
This in the definition of NPC. What you have to prove is that a language is in NPC.
This was proved for SAT first: http://en.wikipedia.org/wiki/Cook%E2%80%93Levin_theorem
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#144Earlier 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…
factorization of course as it has never been demonstrated to be polynomially reducible to NPC.
Every NP problem is polynomial-time reducible to SAT. I do not recall the title of the paper off the top of my head, but it has been proven that the definition of an NP problem (a question that can be answered given some additional piece of information, a "certificate") is polynomial-time reducible to SAT.
The methodology was basically an algorithm taking as input a description of such a solution, and producing a boolean expression on the certificate and some other values needed to maintain integrity. The expression is satisfiable if and only if the answer is affirmative.
The reason that factorization is not known to be NP-complete is that the reverse is not known. That is, no NP-complete problem is known to be polynomial-time reducible to factorization.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#145Earlier 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 …”.
It's been proven that if P != NP, then there are problems in NP, which are neither in P nor NP-complete. We don't know what those problems are, because identifying such a problem would prove P != NP. There are candidates, such as factoring, for which there are neither polynomial algorithms nor proofs of NP-completeness, but definitively identifying them is at least as hard as proving P != NP, and possibly harder.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#146Earlier quoted context omitted.
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…
From what I understand they a 'thought to be' the toughest but this isn't proven. Yes, it is. Any NP problem can be many-one reduced to SAT, which means that there's a function that transforms an instance of the NP problem to an instance of SAT, and the answer to whether that formula is satisfiable is the same as whether that instance is a member of the NP problem (in its decision version). So who is still standing a…
To be pedantic, not all problems in P are equally hard. Sorting for example is harder than finding the median.
The provable lower bound for the worst-case performance of searching is O(n log n). Finding the median takes linear time i.e. O(n).
Sorting and finding a median reduce to each other polynomially, of course.
Interesting subsets of polynamial problems are e.g. linear problems, or highly parallelizeable problems whose runtime tends to O(log n) as the number of processors tends to infinity. Adding a list of numbers is not only linear but also highly parallelizeable. Proving a problem to be not parallelizeable like that, is also interesting.
There's also the question whether randomness helps. It does in practice, but we don't know whether access to random bits helps in theory.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#147Earlier quoted context omitted.
From what I understand they a 'thought to be' the toughest but this isn't proven. Yes, it is. Any NP problem can be many-one reduced to SAT, which means that there's a function that transforms an instance of the NP problem to an instance of SAT, and the answer to whether that formula is satisfiable is the same as whether that instance is a member of the NP problem (in its decision version). So who is still standing a…
To be pedantic, not all problems in P are equally hard. Sorting for example is harder than finding the median. The provable lower bound for the worst-case performance of searching is O(n log n). Finding the median takes linear time i.e. O(n). Sorting and finding a median reduce to each other polynomially, of course. Interesting subsets of polynamial problems are e.g. linear problems, or highly parallelizeable problem…
By "as easy as each other" I meant reducible to each other with a polynomial factor, as is standard in complexity theory.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#148Earlier quoted context omitted.
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 polyn…
Can you supply a link to the proof that all NPC problems are equivalent? I remember learning it, but I can't remember how it worked.
By definition, a problem P is NPC if:
a. P is in NP, and
b. Every problem in NP can be converted to an instance of P.
Consider any two problems in NPC, P and Q. Then each is in NP, and each can be converted to the other. They are therefore equivalent.
QED.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#149Where 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'd put some money on `He hasn't proved P=NP.' as long as the odds are greater than zero.
Re: The polynomial algorithm for 3-SAT problem (or P=NP)
#150Earlier quoted context omitted.
To be pedantic, not all problems in P are equally hard. Sorting for example is harder than finding the median. The provable lower bound for the worst-case performance of searching is O(n log n). Finding the median takes linear time i.e. O(n). Sorting and finding a median reduce to each other polynomially, of course. Interesting subsets of polynamial problems are e.g. linear problems, or highly parallelizeable problem…
By "as easy as each other" I meant reducible to each other with a polynomial factor, as is standard in complexity theory.
Yes, that why I prefaced with "To be pedantic". I just felt like pointing out that there are meaningful differences between polynomial problems.