CODEWITHSUNDEEP
complexity-theorynp
jarnald
jarnald

Reputation: 41

Why is NP only a set of decision problems?

Taken from Wikipedia but all definitions I have seen are similar to this:

"NP is the set of decision problems where the "yes"-instances can be accepted in polynomial time by a non-deterministic Turing machine."

Why is NP restricted to only decision problems? Is it?

Lets take subset sum as an example:

(type 1) Decision problem - Is there a subset B of A that sums up to k?

(type 2) "Normal" problem - what is the subset B of A that sums up to k?

I write "Normal" on type 2 there because that feels like what you usually do when you solve such a problem.

Am I right in understanding, using the definition of NP, that type 1 is in NP while type 2 is not?

It feels like the definition would work equally well in the way it is sometimes written informally

"All problems whose solutions can be checked in polynomial time".

(I found a similar question but it didn't really seem to answer this question)

Upvotes: 3

Views: 1900

Answers (2)

officialgupta
officialgupta

Reputation: 668

A short explanation of what P=NP is:

  • A yes or no problem is in P [Polynomial time] if the answer can be computed in polynomial time.
  • A yes-or-no problem is in NP [Non-deterministic Polynomial time] if a yes answer can be verified in polynomial time.

You can read a bit more about P=NP in my short article: https://medium.com/@officialgupta/what-is-p-np-2b0fd7b9bd83

Upvotes: -1

templatetypedef
templatetypedef

Reputation: 373082

You are right that NP is a class of decision problems (problems with a yes-no answer), so problem (1) is in NP and problem (2) is not in NP. Part of the reason for setting up NP this way is historical (formal language theory concerns questions about whether or not strings/natural numbers belong to a particular set), part of it is for mathematical simplicity (because these problems have only yes/no answers, you can talk about a problem as just the set of "yes" instances and perform set-theoretic operations on those sets), and part of it is to make certain definitions much easier to work with (reducibility, for example, is really easy to express from a language perspective).

This isn't to say that more general problems aren't interesting - they absolutely are! The problem of type (2) that you've described might not be in NP, but it is in a complexity class called FNP (function NP), which is a natural generalization of NP to the case where the job is to find a particular object satisfying criteria that can be checked in polynomial time. There's also a corresponding version of class P called FP, and there's a corresponding FP versus FNP problem.

Upvotes: 4

Related Questions