Talk:P versus NP problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Spoken Wikipedia
WikiProject icon This article is within the scope of WikiProject Spoken Wikipedia, a collaborative effort to improve the coverage of articles that are spoken on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 

If P = NP, P ≠ NPC[edit]

The diagram in the section about NP-Completeness (http://en.wikipedia.org/wiki/P_versus_NP_problem#mediaviewer/File:P_np_np-complete_np-hard.svg) shows wrongly that if P = NP, P = NPC. Proof: take the empty language Ø, a problem in P. No other language can ever be reduced to Ø, because yes-instances of that problem cannot be mapped to yes-instances of Ø. Therefore, Ø can never be in NPC because that would be every other language in NP could be reduced to it.

I say we remove the image.

Blum's proof seems unlikely to stand[edit]

Before adding Blum's proof again, it seems very likely it will not stand. In particular, the heart of Blum's proof is Theorem 6, which says that the bounds for a monotone circuit (where we know we need exponential size) can also be applied to a general circuit. However, the Tardos function is an explicit counterexample to this theorem. It takes exponential size monotone circuits, but only polynomial size general circuits. See here. So at the very least we should wait for more analysis before adding this. LouScheffer (talk) 14:54, 25 August 2017 (UTC)

Semi-protected edit request on 8 September 2017[edit]

In the section: Does P mean "easy"? Is says that traveling salesman problem is NP-complete

Quote: There are algorithms for many NP-complete problems, such as the knapsack problem, the traveling salesman problem

But I think it is NP-hard. (It says that if you look at the wikipedia entry for that problem) It is an optimization problem, so I understand that it is NP-hard 200.40.231.41 (talk) 20:50, 8 September 2017 (UTC)

Not done: it's not clear what changes you want to be made. Please mention the specific changes in a "change X to Y" format. — nihlus kryik  (talk) 21:05, 8 September 2017 (UTC)
The words "travelling salesman problem" refer to two different things: the optimization problem mentioned in the first paragraph of the article travelling salesman problem, but also the decision problem mentioned in the third paragraph. The latter problem is a decision problem, and is NP-complete. If you had a non-clunky way to disambiguate these two in context, I'm sure people would be open to adjusting the wording. --JBL (talk) 21:30, 8 September 2017 (UTC)

Consequences of a Solution: P = NP - One-Way Functions[edit]

I recommend that we link to cryptographic hash functions instead of one-way functions. My concern stems from inconsistent use of the term "one-way function". As things stand, the reader is told that, essentially, a consequence of P=NP is that "one-way functions" would no longer be useful. This reader might then go to the relevant article only to discover that P=NP would actually imply that the functions we called one-way functions in the P versus NP article were not actually one-way functions at all and that no such functions existed in the first place (the one-way function article only talks about the strict definition of the term). Additionally, since it isn't mentioned that the term "one-way function" is only loosely applied to things like hash functions, the reader doesn't really have an obvious explanation for what this confusing situation means. Thoughts? Jwuthe2 (talk) 04:26, 9 November 2017 (UTC)

In defense of adjectives[edit]

At least one of the editors here believes the words "seminal", "informal", and "suitably" should be deleted, as these are opinions. I will argue the opposite here, explaining why I think they are helpful, well supported by reliable sources, and add value to a Wikipedia reader. Discussion of this point is of course welcome.

I agree these words are not valuable to a reader already familiar with the topic. They know already what papers are important and led to lots of future research, they understand that quickly is not formally defined, they are already impressed that Nash thought the problem of showing some problems take exponential time is really hard to prove, long before folks spent careers trying to prove it and (so far) being unable to.

But to the kind of reader who comes to Wikipedia to find out about a topic, these words are extremely helpful.

  • Seminal tells the reader this a really important paper. If you want to understand the field further, start with this. In many textbooks (including ones that are extremely technical, such as Gravitation by Misner, Thorne, and Wheeler) the important results are marked in bold. Seminal is a textual way of doing this. Note that the dictionary meaning of seminal includes the example "his seminal work of chaos theory". This would be the 1890 article of Poincare, which has about 1200 cites. The paper quoted here has about 7000 cites, so seminal is well supported.
  • Informal is very helpful here as well. Quickly means very different things to different scientists. Hydrogen-4, for example, decays quickly in about 10-24 seconds. Black hole binaries decay quickly in about 1017 seconds. This is why quickly is not defined scientifically - it's relative to something, which is implied by the context. Polynomials also vary over a 1041 range, or more, but they are formally defined and not relative to a context. This distinction is helpful to the (novice) reader.
  • Suitably is helpful to point out to the reader that Nash's skepticism was the result of his good intuition. The formal problem was not even well defined for two more decades, and he did not have the advantage of knowing that lots of smart people had tried to prove it for decades, without success.

The view of other editors would be interesting here. LouScheffer (talk) 18:01, 23 November 2017 (UTC)

"Informal" and "suitably" are just normal descriptive words that should be unobjectionable in any context. "Seminal" is an editorial judgement that requires reliable sourcing. But for this problem, such sourcing is easy to come by. I agree that removing all adjectives and adverbs, in a misguided sense that by doing so we are being more factual, is a mistake. It removes important information from the article, both in the form of helpful guidance for the reader ("informal") and on this subject's position in the academic literature ("seminal"). —David Eppstein (talk) 18:26, 23 November 2017 (UTC)
This is the third or fourth talk page discussion of precisely this issue in the last 16 months. There is a clear (and correct) consensus in favor of the adjectives and adverbs in question. The opposition to this consensus comes from an ip-hopping user who was banned for good reason. In this context, there is nothing to discuss, the ip editor should be treated as a run-of-the-mill vandal and be reverted on sight. --JBL (talk) 01:26, 24 November 2017 (UTC)

Pure Logic[edit]

The problem examines whether problems whose solutions can be verified quickly can also be solved quickly. Are there any academic sources on the pure logic of the problem? I am no academic, but it seems to me there are real world corollaries. For instance if one's problem was being cold the solution might be starting a fire. But just because it is easy to check if a fire is burning, doesn't necessarily mean it's easy to start a fire. But sometimes lightning strikes and through no effort of our cold being the fire is started, and the problem is solved. — Preceding unsigned comment added by 216.70.34.130 (talk) 17:28, 2 December 2017 (UTC)

No, this vague philosophizing has nothing to do with P vs. NP. --JBL (talk) 18:35, 2 December 2017 (UTC)
There are actually very strong connections between this problem and mathematical logic, though, via descriptive complexity. In particular, Fagin's theorem states that NP is the class of properties expressible in existential second-order logic, so some complexity-theoretic questions involving NP (especially whether NP = coNP) have clean formulations in logic. The logical characterizations of P itself, however, are somewhat messier. —David Eppstein (talk) 03:16, 3 December 2017 (UTC)
Physical models where it's easy to see a result, but hard to generate it (such as a hole-in-one in golf, or an atomic bomb explosion) are not difficult in the computational sense - it's easy to see how the solutions should work. What is difficult is generating the initial conditions that are known to be needed. This can be due to extreme sensitivity to initial conditions (as in golf), or conditions that are rarely obtained naturally (atomic bomb). The first is more naturally studied as chaos theory and the second as engineering. Study of P =? NP, or even a solution in either direction, would have little effect on how these problems are addressed. LouScheffer (talk) 15:24, 3 December 2017 (UTC)