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
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
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.
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
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