-1

Among P, NP, NP hard and NP-complete, only the NP-complete set is restricted to decision problems (those that have a binary solution). What is the reason for this? Why not define it simply as the intersection of NP and NP-hard? And this leads to another question - there must be problems that are not necessarily decision problems and also have the property that any problem in NP can be reduced to them in polynomial time. Is this then a set encompassing NP-complete? Is there already a name for this set?

EDIT: Per the comment by Matt and also the post: What are the differences between NP, NP-Complete and NP-Hard?, its seems P and NP are defined only for decision problems. That would resolve this question apart from why they would be defined this way. But, this seems to be in contradiction to the book Introduction to Algorithms by Cormen et.al. In chapter 34, the section titled "NP-completeness and the classes P and NP", they simply say: "P consists of those problems that are solvable in polynomial time". They even say later, "NP-completeness applies directly not to optimization problems, but to decision problems" but say no such thing about P and NP.

Rohit Pandey
  • 2,443
  • 7
  • 31
  • 54
  • P and NP are also restricted to decision problems. NP-complete *is* the intersection of NP and NP-hard – Matt Timmermans Oct 02 '22 at 00:34
  • Oh, I didn't know this. So the problem of sorting an array is not in P? This seems unnatural to me. Why define P only for decision problems? – Rohit Pandey Oct 02 '22 at 00:35
  • 1
    So that we can ask if P=NP... – Matt Timmermans Oct 02 '22 at 00:38
  • I see. It isn't immediately obvious to me why we wouldn't be able to ask this if these sets pertained to optimization problems. Let me think about it. – Rohit Pandey Oct 02 '22 at 00:40
  • Also, this seems to be in contradiction of chapter 34 of Introduction to Algorithms by Cormen et.al. The section "NP-completeness and the classes P and NP". – Rohit Pandey Oct 02 '22 at 00:48
  • To "beg the question" is to re-use the initial question as an answer. "Why do roosters crow in the morning? Because it is sunrise, would beg the question as it doesn't actually answer why". To "beg the question" does NOT mean "here is a question that follows on logically from the previous conversation". – Enigmativity Oct 02 '22 at 00:49
  • Sure, edited to remove that phrase. – Rohit Pandey Oct 02 '22 at 00:52

1 Answers1

1

The classes P and NP are indeed classes of decision problems. I don’t have my copy of CLRS handy, but if they’re claiming that P and NP are all problems solvable in polynomial time or nondeterministic polynomial time, respectively, they are incorrect.

There are some good theoretical reasons why it’s helpful to define P and NP as sets of decision problems. Working with decision problems makes reducibility much easier (reducing one problem to another doesn’t require transforming output), simplifies the model by eliminating issues of how big the answer to a question must be, makes it easier to define nondeterministic computation, etc.

But none of those are “dealbreakers” in the sense that you can define analogous complexity classes that involve computing functions rather than just coming up with yes or no answers. For example, the classes FP and FNP are the function problem versions of P and NP, and the question of whether FP = FNP is similarly open.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • You can access the book here (for now): https://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_(2009).pdf. It seems strange that they would make such a glaring mistake. What is a function problem? – Rohit Pandey Oct 02 '22 at 04:47
  • Also, can you point to any textbook that defines P and NP as containing only decision problems? – Rohit Pandey Oct 02 '22 at 04:51
  • And finally, is there an FNP-Complete class as well then? – Rohit Pandey Oct 02 '22 at 05:06
  • 1
    Most intro textbooks on computability or complexity will have this definition. Check out *Introduction to the Theory of Computation* by Michael Sipser or *Automata, Languages, and Computation* by Hopcroft, Motwani, and Ullman. A function problem is one where the goal is to compute some value based on an input. So, for example, “compute x + y” is a function problem but not a decision problem. And yes, there are FNP-complete problems. – templatetypedef Oct 02 '22 at 15:06