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
This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||
|
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.