Is it necessary for NP problems to be decision problems?

Question

Professor Tim Roughgarden from Stanford University while teaching a MOOC said that solutions to problems in the class NP must be polynomial in length. But the wikipedia article says that NP problems are decision problems. So what type of problems are basically in the class NP ? And is it unnecessary to say that solutions to such problems have a polynomial length output(as decision problems necessarily output either 0 or 1) ?

Answer 1

Indeed problems in NP are decision problems which output 0 or 1 for a given input string. Prof Roughgarden is referring to the fact that problems in NP have short polynomially bounded proof (in the input length) of membership that can be verified efficiently (by polynomial time algorithm).

Answer 2

Yes, NP is commonly only defined for decision problems

In the commonly used definition of an NP problem, the answer can only be yes or no, as given on Wikipedia https://en.wikipedia.org/wiki/NP_(complexity):

In computational complexity theory, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems.

This is also made more explicit at:

Many computer science problems are contained in NP, like decision versions of many search and optimization problems.

where e.g. the "search version" of the problem means "find the solution if it exists".

To give a concrete example, we could think of:

• is a given boolean formula satisfiable? Decision version of SAT.
• find an assignment for this formula if one exists. Search version of SAT.

Search problems have dedicated classes called FNP and TFNP

Since NP does not cover search problems, there is a specifically named complexity class for search problems called FNP which the Wikipedia page defines as:

A binary relation P(x,y), where y is at most polynomially longer than x, is in FNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(x,y) holds given both x and y.

So here for a concrete SAT example you could think of:

• x as an boolean formula
• y as an assignment that satisfies the formula

Besides FNP, there is also the related TFNP class, for which an answer always exists. An example of this is the version of the integer factorization problem:

P(x, y): x is an integer, and y is the list of all divisors

This version of the problem always has a trivial solution: 1 and x!

Note that we could however also formulate integer factorization as an FNP problem:

P(x, y): x is an integer, and y is a non-empty list of all divisors > 1 and < x

where there is no solution for prime numbers.

For every NP problem there is an FNP problem and vice versa

For every FNP search problem we can trivially make up a corresponding NP decision problem, this is trivial

for a given problem x, does a solution y exist that satisfies x

And conversely, for every NP problem there is a FNP problem. This is because from the definition of an NP problem, there is a verifier V(x, y) which checks if y is a solution to problem instance x. And so we formulate the FNP problem as:

P(x, y) = V(x, y)

To be more precise, the FNP of an NP problem might not be unique, since there might be multiple correct answers for a given satisfiability decision.

You can always reduce an FNP problem to an NP problem in polynomial time by bisection

So from this, we see that there is a fundamental equivalence between NP and FNP problems, which gives precise meaning to informally saying that an FNP problem "is NP".

This reduction is trivial and generally useless in practice however.

For example, consider the FNP version of integer factorization.

And then consider the NP problem:

Does integer x have a non-trivial factorization where the largest factor is larger than a chosen value z?

Note that now the input of the NP problem is a pair: (x, z), not just x.

If we could solve the above problem, we could just bisect the largest factor of x, divide x by it, and continue until the last factor.

Note that on the above reduction, we did use the property of the specific factorization problem that we can divide x by its factor to make the problem smaller, but this is not needed in general.

We just have to think as:

• the solution to every problem is a string of 0s and 1s which can be interpreted as an integer
• the size of the solution has to be polynomially bound by the size of the input, otherwise we wouldn't be above to verify it in polynomial time

Once solutions are encoded like this, we must have a maximum solution for a given problem, M. And so we just create an NP problem as:

Is there a solution encoded as a number larger than M/2

and bisect like that.

An FNP problem might be fundamentally harder than its (non binary cheat) decision version

On the previous section, we saw that a reduction from FNP to an associated bisection decision problem is always possible in P.

However, if we consider more strictly only the exact decision problem without that extra bisection parameter, this is believed to not hold.

The trivial bisection reduction is generally useless, as it is possible that some non-bisection reductions could always be harder than the FNP problem. This is to be expected since the bisection exists for any problem, without using any properties of the problem.

One notable example is integer factorization, in which we know that the non-bisection NP version of the FNP problem, i.e.: "is the number prime", can be solved in polynomial time due to the AKS primality test.

Therefore, this serves as an example in which the FNP problem could be fundamentally harder than the non-bisection version of the problem, since it is currently believed that integer factorization is not in P (but also not NP-complete).

It is worth noting that in other cases however, the FNP problem can reduce to the non-trivial-bisection NP problem. https://blog.computationalcomplexity.org/2019/01/search-versus-decision.html mentions that this is the case for example of graph isomorphism (which like integer factorization is thought to be NP-intermediate). Such problems are called self-reducible. The proof of self-reducibility has been asked at: Why is Graph Isomorphism downward self reducible?

Furthermore, the wiki page for FNP mentions that this has actually been proven:

Bellare and Goldwasser showed in 1994 using some standard assumptions that there exist problems in NP such that their FNP versions are not self-reducible, implying that they are harder than their corresponding decision problem.

If the associated NP problem of an FNP-problem is NP-complete, we can always reduce the FNP to the NP problem in polynomial time

Shown at https://cseweb.ucsd.edu/~mihir/cse200/decision-search.pdf "4 Decision vs Search for NP-complete languages".

For example for SAT, we could just set one variable to true and false, and then do the decision problem on a smaller problem. We then pick the value that works if any, and continue with that and the smaller problem with one less variable.

Then the argument goes along the "every NP Problem can be reduced to SAT" lines.

Note however that this is only known to be true in general for NP-complete decision problems! For example in integer factorization, the decision problem is P, while the search problem is believed to not be in P.

TFNP appears to be easier than FNP

As mentioned on the wiki page https://en.wikipedia.org/wiki/TFNP there are no known NP-hard problems known to be in TFNP, while there are obviously NP-hard FNP problems (e.g. SAT).

It is also worth noting that there isn't a trivial way to convert a TFNP problem to an NP problem like there is for FNP problems, because now we can't just use the "is there a solution" conversion.

You can always add an extra restriction to the TFNP problem that knocks off some solutions to reach a FNP problem however, like we did for integer factorization (exclude empty lists and 1 and N), but then the question is if you can still use that restricted solution.

Decision problems form languages

Another "philosophical" motivation for NP dealing only with decision problems is that the yes/no decision leads maps better in the concept of a formal language accepted by a Turing Machine: the formal language is the set of all strings accepted by the given machine (terminates and outputs yes on the tape).

Notably Turing complete languages are at the top of the Chomsky hierarchy, which has been an useful tool to classify the parsing complexity programming-like languages.

Related questions

• Decision problems vs "real" problems that aren't yes-or-no question body talks about optimization, and so do answers, but I'm more interested in search
• Optimization version of decision problems are talking about optimization and NP-hard problems, which are not the case of integer factorization
• What is the definition of P, NP, NP-complete and NP-hard? just too generic
• https://cstheory.stackexchange.com/questions/37812/what-exactly-are-the-classes-fp-fnp-and-tfnp