Talk:NP-easy

From Wikipedia, the free encyclopedia

I find the requirement that NP-easy problems cannot be decision problems a bit odd, since the boundary of the set of decision problems is shady. Consider for instance the problem

input: positive integer n

output: YES if n is prime, NO otherwise

Clearly a decision problem. But

input: integer n

output: YES if n is positive and prime, NO if n is positive and composite, NONPOSITIVE if n is not positive

It's not a decision problem, but for all practical purposes it's completely identical.

Can't we just allow decision problems as members of NP-easy, so that we get NP ⊆ NP-easy? Here are two references that seem to do that: http://www.cs.caltech.edu/~cs20/B/exams/Final-2001b.ps http://www.cs.pitt.edu/~kirk/cs1510/notes/reducenotes/node6.html

Yes, the set does include decision problems. I've changed that now. The book I have said otherwise, but from the way it's written, I now think that was unintentional. The two URLs above don't look like the best sources, though. In the final exam, the true/false question (x) is clearly false no matter how the terms are defined. In the page from the lecture notes, it starts off For our purposes we use NP-complete and NP-equivalent interchangeably, although there is a technical difference that's not really relevant to us. I'm not sure I'd want to consult that source for questions like this.

[edit] example for a NP-easy problem

Sorting can be done in polynomial time, thus it is of course an example for a NP-easy problem. The example is only helpful to confirm the intution everybody has anyway. However, I think it would be better to mention a problem which makes it clear that NP-easy is not just a way to extend the class NP from decision problems to non decision problems but that it also contains decision problems which are not in NP. I think co-3-SAT is a good example since it shows that the class of NP-easy problems contains also all problems from co-NP.