This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
The article said:
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)
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)
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)
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)
Pigeonhole Subset Sum is known to be NP-Complete. See [1]. Bcroner ( talk) 17:58, 9 September 2020 (UTC)
References
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)
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||
|
The article said:
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)
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)
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)
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)
Pigeonhole Subset Sum is known to be NP-Complete. See [1]. Bcroner ( talk) 17:58, 9 September 2020 (UTC)
References
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)