Talk:NP-intermediate

(Redirected from Talk:Ladner's theorem)
Latest comment: 2 years ago by David Eppstein in topic Decision problem or not?

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

  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

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