0
$\begingroup$

This question already has an answer here:

We know that NP is the class of languages recognized by a nondeterministic Turing machine (NTM) in polynomial time. I've also read that NP is the class of problems can be solved by NTM in polynomial time. It is clear that every decision problem can be seen like a recognition language problem, but if we have a function problem (given $x$ find $y=f(x)$) what can we say?

In short, let $A$ be the decision problems solved by NTMs in polynomial time and $B$ be the function problems solved by NTMs in polynomial time. Is NP equal to $A$ or $B$ or both?

$\endgroup$

marked as duplicate by Raphael Jan 17 '18 at 20:17

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2
$\begingroup$

NP is a class of languages and languages correspond to decision problems. Specifically, any language $L$ corresponds to the decision problem, "Here's a string $x$. Is it in $L$?"

$\endgroup$
  • $\begingroup$ Then in this link en.wikipedia.org/wiki/NP_(complexity) at paragraph "Equivalence of definitions" when says "The two definitions of NP as the class of problems solvable by a nondeterministic Turing machine (TM) in polynomial time and the class of problems verifiable by a deterministic Turing machine in polynomial time are equivalent." it means class of decisional problem? $\endgroup$ – asv Jan 17 '18 at 15:42
  • $\begingroup$ That's correct -- any definition of NP that is equivalent to the standard one must be a set of decision problems. $\endgroup$ – David Richerby Jan 17 '18 at 16:38
1
$\begingroup$

NP by definition is the class of decision problems solvable in polynomial-time on a non-deterministic Turing machine. So, by definition, NP is your $A$ set. NP can't also be $B$ for superficial reasons: NP is a subset of functions $2^*\to 2$, and so it simply doesn't contain any functions $2^*\to2^*$ whose output isn't always one bit long.

There is a separate class FNP for the class of search problems solvable in polynomial-time on a non-deterministic Turing machine. A decision problem $\varphi$ is in NP when $$\forall x\in 2^*.\varphi(x)\iff \exists u\in2^{p(|x|)}.M(x,u)=1$$ for some polynomial $p$ and polynomial-time (deterministic) Turing machine $M$. A function $f$ is in FNP if given $x$ it finds a $u$ such that $M(x,u)=1$. Note, there is no constraint on how much time $f$ takes to produce a $u$ from $x$. That said, on a non-deterministic Turing machine, we can just guess the bits of $u$ and then check them against $M$ in polynomial-time. (We can cast an arbitrary function computed in polynomial-time on an NDTM $F$ as the relation $R(x,\langle u,y\rangle)\iff F(x,u)=y$ where $u$ represents the non-deterministic choices which is calculable in polynomial-time simply by simulating $F$ with choices $u$.)

As mentioned on the Complexity Zoo page, The Complexity of Decision Versus Search shows that if EE $\neq$ NEE or (citing a different result) if NE $\neq$ coNE then there are problems in FNP that can't be reduced to corresponding decision problems in NP in the sense if for any suitable machine $M$ we're provided an oracle for $\varphi(x)\equiv\exists u\in 2^{p(|x|)}.M(x,u)=1$ we could compute in polynomial-time some $u$ for the particular $x$ we were given such that $M(x,u)=1$. Any decision problem whose corresponding search problem is reducible to the decision problem can't be NP-complete: given an oracle for an NP-complete problem, we'd then be able to efficiently compute SAT whose search problem we can reduce to the corresponding decision problem, and which we can then use to compute the $u$ for the original problem by reducing it to SAT.

So the focus on decision problems doesn't seem completely innocuous, but we do have P = NP $\iff$ FP = FNP, so for at least the P = NP problem it doesn't matter. This can be partially seen from the above since if P = NP then every problem in NP is NP-complete and the counter-example to the reduction of search to decision doesn't exist.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.