Talk:NP-intermediate

This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles 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.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles

Mid

This article has been rated as Mid-importance on the project's importance scale.

Things you can help WikiProject Computer science with:

Here are some tasks awaiting attention:

Article requests :
- Requested articles/Applied arts and sciences/Computer science, computing, and Internet
Cleanup :
- Computer science articles needing attention
- Computer science articles needing expert attention
Copyedit :
- Computing
Expand :
- Computer science
Infobox :
- Computer science articles without infoboxes
Maintain :
- Timeline of computing 2020–present
Photo :
- Find pictures for the biographies of computer scientists (see List of computer scientists)
- Computing articles needing images
Stubs :
- Computer science stubs
Unreferenced :
- WikiProject Computer science/Unreferenced BLPs
Project-related :
- Tag all relevant articles in Category:Computer science and sub-categories with {{WikiProject Computer science}}

Mathematics Stub‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics 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.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
Stub	This article has been given a rating which conflicts with the project-independent quality rating in the banner shell. Please resolve this conflict if possible.
Low	This article has been rated as Low-priority on the project's priority scale.

Weasel words[edit]

The article said:

No natural problem is currently known to have this property.

No problem, natural or not, is known to have this property. If any were, it would a fortiori be a proof the P≠NP. I have removed the weasel word "natural". -- Dominus 20:06, 5 April 2006 (UTC)[reply]

The property was: "of being in NP-(NP-hard + P) in case P!=NP", so some problems are known to have this property. The point was whether some problem that have been actually considered in practice have this property. I will have a check of how this is formulated in the books. Well, maybe "considered in practice" is a good alternative? - Liberatore(T) 20:20, 5 April 2006 (UTC)[reply]

Oh, I see. The original wording is ambiguous, and I read it the wrong way. One could take "this property" to be the property ' x∈NP ∧ ¬(x∈NPC), or "this property" could be P≠NP → ( x∈NP ∧ ¬x∈NPC ). Both are interesting; I took it to mean the former, but the latter was intended. Thanks for pointing this out.

I have no objection to the word "natural" in the way it was intended now that I understand what was meant. But I do think the article needs to be reworded to avoid the ambiguity in phrasing. -- Dominus 18:02, 6 April 2006 (UTC)[reply]

The original version was indeed misleading. I have expanded the article a bit to avoid ambiguities. - Liberatore(T) 13:14, 7 April 2006 (UTC)[reply]

No, it still doesn't seem to make sense. We're told that if P ≠ NP then NPI is nonempty. Is the converse true? If so, then the statment "none of these problems has been shown to be in NPI" seems rather superficial if we don't yet have a proof that P ≠ NP. If not, then maybe this (i.e. that NPI can be nonempty even if P=NP) is something that should be stated explicitly. Jowa fan (talk) 04:35, 13 August 2010 (UTC)[reply]

NPI is a subset of NP \ P, so if P = NP then it is trivially empty. Yes, you're right, showing the existence of a problem in NPI would be a proof that P ≠ NP. However, it could potentially be shown that some natural problem is in NPI under the assumption that P ≠ NP, without proving the latter. I think the wording in the article was intended to convey that this hasn't been done. --David-Sarah Hopwood ⚥ (talk) 02:27, 21 August 2010 (UTC)[reply]

I recently tried to be more explicit and less redundant about this issue. Do you (Jowa fan) think it is better now? Bender2k14 (talk) 03:52, 6 September 2010 (UTC)[reply]

As someone who's not an expert on the subject, the quote "Ladner's proof explicitly constructs an NP-intermediate problem" puzzled me until I read over the article a few times. I initially interpreted it as saying he had constructed a problem that he proved was in NPI, which would in turn prove P!=NP. Since that clearly isn't the case, I assume it is supposed to mean he proved that the problem is in NPI iff P!=NP. Is that correct? Imyourfoot (talk) 07:03, 11 February 2011 (UTC)[reply]

That seems to be the only reasonable explanation, I would like to see this clarified, however. —Ruud 23:36, 19 March 2011 (UTC)[reply]

Speaking for myself, Richard Ladner, I might reword the one sentence that is causing problems to "Under the assumption that P!=NP, Ladner explicitly constructs a problem in NPI, however ..." Finally, a problem like graph isomorphism can be a candidate to be a member of NPI, if it is in NP and not known to be NP-complete nor in P. Of course such a problem is also a candidate for being a member of P or possibly NP-complete. —Preceding unsigned comment added by 128.208.2.65 (talk) 22:00, 18 April 2011 (UTC)[reply]

Pigeonhole Subset Sum is known to be NP-Complete. See ^[1].Bcroner (talk) 17:58, 9 September 2020 (UTC)[reply]

References

^ Woeginger, Yu. (July 1992). On the equal-subset-sum problem. Information Processing Letters, Volume 42, Issue 6, p. 299-302. https://doi.org/10.1016/0020-0190(92)90226-L

Decision problem or not?[edit]

The way the article defines them, NP-intermediate problems would all have to be decision problems, since P and NP are both classes of such. Yet most of the candidates listed are not decision problems! Sometimes there is a straightforward decision problem counterpart of a more general problem, but in the case of for example integer factorisation I have no idea what that would be; testing an integer for being composite is already in P, so that can't be it. 90.129.219.218 (talk) 14:36, 8 February 2022 (UTC)[reply]

There are standard decision problem versions of factorization. For instance, is there a factor between 2 and x? Asking that question repeatedly would allow you to recover the factorization itself by binary search. —David Eppstein (talk) 17:26, 8 February 2022 (UTC)[reply]

[1] Woeginger, Yu. (July 1992). On the equal-subset-sum problem. Information Processing Letters, Volume 42, Issue 6, p. 299-302. https://doi.org/10.1016/0020-0190(92)90226-L

[1]