Talk:P versus NP problem

Euler diagram blatantly wrong.

I'm removing the Euler diagram for reasons I've spelled out on its discussion page. Twin Bird (talk) 23:06, 23 July 2011 (UTC)

Sadly, your reasons are very mistaken. If P=NP, then every decision problem in NP (with two trivial exceptions, the problem in which the answer is always "yes" and the problem in which the answer is always "no") would become NP-complete. The reason is that, in that case, if X is any problem in NP other than these two exceptions, y is an instance of X for which the answer is "no", and z is an instance of X for which the answer is "yes", and if W is any other problem in NP, then there is an easy polynomial time many-one reduction from W to X: solve W in polynomial time and then output either y or z as appropriate. Since a polynomial time many-one reduction exists from anything in NP to X, X is NP-complete. —David Eppstein (talk) 00:00, 24 July 2011 (UTC)

P=NP sometimes

"P=NP where N=1" :-) (scroll the linked text up to page 134.) The text has other items related to the discussions in this talk page, such as "The impossibility of a proof of the impossibility of a proof." Max Longint (talk) 16:26, 6 October 2011 (UTC)

Useful Cartoon?

I am conflicted on actually editing this article, so I will ask you other editors if this cartoon would make this article friendlier to people who know of this P versus NP problem but can't handle any math (like me).

LadyJosie (talk) 16:12, 21 December 2011 (UTC)

The discussion page is loaded with math http://commons.wikimedia.org/wiki/File_talk:Relativistic_P_%3D_NP_Computation.png. Doug says he modified a Minkowski Diagram / Twin Paradox and he can make changes to the figure (MS Power Point) as might be suggested here. All I did was watch and proof English! None of the Minkowski Diagrams on Commons were fully PD. This one is. There will be a published reference, soon. I'll update here as it is published on Amazon Kindle as an e-book. LadyJosie (talk) 16:48, 21 December 2011 (UTC)

No, this cartoon doesn't belong in the article. If you can reference it and produce the reference, explaining the significance, it might be appropriate. Andrevan@ 04:51, 24 December 2011 (UTC)

No, the idea that relativistic time dilation can be used for exponential speedup in computation is not mentioned in this article, because it is highly speculative (and I'm pretty sure there are good arguments against it being possible without exponential energy). There is some discussion of such things at hypercomputation. A proper general discussion of time dilation's relation to computation would belong in another article than this one. More to the point, the terminology in this diagram is nonsensical (e.g. "start an NP calculation with my P algorithm"), to the point where I can't tell what the intended meaning was. Dcoetzee 05:26, 24 December 2011 (UTC)

No, but after publication and clarification, "yes" as an external link. As far as I can tell, Youvan is trying to describe something very trival by relating Einstein's time dilation effect to waiting for a slow "P" algo to do the work of a hypothetical, fast "NP" algo while the traveler is away, near v = c, and then returns to see that the "P" algo has finished. In the traveler's time frame, the calculation looked quick, although it might have scaled as N! or worse on the ground. In the static time frame, the calculation took a very long time. It's just the Twin Paradox combined with P v NP. Noncanonical (talk) 03:45, 31 December 2011 (UTC)

Youvan has updated his e-book to include a new reference which arrives at the same conclusion:

t_NP = t_P (1 – (v_NP ²/ c²))^0.5 . (Eq. 1) - from Youvan ISBN 978-0-9849696-0-9, he now quotes:

A similar equation can be found at http://www.hotquanta.com/twinslit.html , hosting a very nice white paper, entitled: “Historic Background & The Twin Slit Example”, by John K. N. Murphy. Noncanonical (talk) 23:12, 4 January 2012 (UTC)

Something is wrong with that hyperlink, above. I'll look into it, soon. Noncanonical (talk) 23:15, 4 January 2012 (UTC)

It seems trivial indeed to me, but it also has no relation to the P vs NP problem in particular. Of course time dilation can be used to accelerate computation from the perspective of an observer in an inertial reference frame. Given sufficient energy (and a means of overcoming technical issues) it could even be sped up by an exponential factor. But this says more about P vs EXP than P vs NP, and the same principle could give arbitrary speedup, or mere constant-factor speedup, depending on the energy invested. That's why I say this is the wrong article to discuss it, and one relating to computation time in general is more appropriate. Dcoetzee 09:22, 6 January 2012 (UTC)

Noncanonical (talk · contribs) was indef blocked after an AN discussion. --Walter Siegmund (talk) 18:46, 7 January 2012 (UTC)

"Mechanical transformation to traveling salesman"

In the section "NP-complete", there was the following sentence: For instance, the decision problem version of the traveling salesman problem is NP-complete, so any instance of any problem in NP can be transformed mechanically into an instance of the traveling salesman problem, in polynomial time.

There is little to no explanation as to how any NP-complete problem can be transformed into an instance of the Traveling Salesman problem (for instance the Knapsack problem). Can anyone edit this section to make it easier to understand?

Bluhd (talk) 20:46, 13 January 2012 (UTC)

While this was in fact true, it was not at all clear, obvious, or easy to prove. Proving it would take us too far afield from the topic at hand, so instead I've replaced it with the boolean satisfiability problem, which is proven to be NP-complete in the article Cook-Levin theorem. The fact that any problem in NP can be polynomial-time reduced to an NP-complete problem is simply part of the definition of NP-complete. Dcoetzee 21:02, 13 January 2012 (UTC)

Polynomial-time algorithms

This section says "It correctly accepts the NP-complete language SUBSET-SUM, and runs in polynomial time if and only if P = NP:". Does it correctly accept the language; and iff P=NP, run in polynomial time? The question is its running time, not its correctness, right? After reading it several times, I'm guessing so, but I'm still a bit unclear about it.--Prosfilaes (talk) 05:57, 8 February 2012 (UTC)

That is correct, and could be clarified. Dcoetzee 07:07, 8 February 2012 (UTC)

Quick check: logic in 3rd paragraph

In the 3rd paragraph it says:

"However, there is no known algorithm to find such a subset in polynomial time [...], and indeed such an algorithm cannot exist if the two complexity classes are not the same."

Shouldn't it be "[...] might not exist [...]"?

I don't know anything about P=NP, so I daren't edit the article. Could someone knowledgeable check this maybe? — Preceding unsigned comment added by 131.111.184.83 (talk) 00:18, 19 February 2012 (UTC)

No, cannot is correct. If P ≠ NP, then polynomial-time algorithms for NP-hard problems do not exist. Dcoetzee 06:24, 19 February 2012 (UTC)