Timeline for Non-existence of algorithm converting NP algorithm to P algorithm?
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 12, 2010 at 1:08 | comment | added | Joel David Hamkins | Antonio, I agree, and it seems that we may be back to square one. | |
| Jun 12, 2010 at 1:04 | comment | added | Antonio E. Porreca | Joel, you’re right. Cook’s reduction of an arbitrary problem in NP to SAT depends not only the NDTM to “simulate”, but also on the polynomial that bounds its running time, which we are not given as input (and we cannot compute from N). Now, not only I don’t see that the map N ↦ M should be polytime, but it’s not clear to me that it can be computable at all. | |
| Jun 12, 2010 at 0:44 | comment | added | Joel David Hamkins | Nate, is your argument correct? There is a hidden uniformity assumption. Given the original nondeterministic algorithm p, we know it reduces to 3-Sat, but how to we know which reduction function does the job? Antonio's suggestion is helpful, but I don't see how it solves the issue, since we do not seem to know how big the coefficients or degree of the reduction polynomial will be, and so we cannot seem to uniformly bound the required size of $\varphi(N,x)$. Thus, I don't see why the map $N\to M$ will be polytime. | |
| Jun 11, 2010 at 23:39 | comment | added | Antonio E. Porreca | @Nate Eldredge: I think there’s a missing step (but maybe it was just implied). The full story should be: given a NDTM N, construct a DTM M which, on input x, builds a Boolean formula φ(N,x), whose meaning is “there is an accepting computation of N on x”, then checks whether it can be satisfied by using the polytime DTM for SAT. The machine M, in turn, runs in polytime. | |
| Jun 11, 2010 at 21:08 | comment | added | Tom Ellis | @David Speyer: so $P = NP$ iff $A$ is polynomial time? | |
| Jun 11, 2010 at 21:06 | comment | added | Tom Ellis | I guess what I need to know is: is the map taking each Turing machine M to (M's reduction to 3SAT) itself a computable map? | |
| Jun 11, 2010 at 21:05 | comment | added | David E Speyer | Moreover, there is a cute fact of Theoretical CS: There is a specific explicit algorithm $A$ such that, if there is any polynomial time solution to $SAT$, then $A$ is a polynomial time solution to $SAT$. See Theorem 2 of scottaaronson.com/blog/?p=392 . So, even if someone were to give a non-constructive proof that $P=NP$, you would still have a completely explicit algorithm to run on the 3SAT problem that Nate constructs. | |
| Jun 11, 2010 at 21:01 | vote | accept | Tom Ellis | ||
| Jun 11, 2010 at 21:05 | |||||
| Jun 11, 2010 at 20:59 | history | answered | Nate Eldredge | CC BY-SA 2.5 |