Function problems and $FP \subseteq FNP$

Question

I find it hard to find formal definitions of function complexity classes. Here are two from Wikipedia.

A binary relation $P(x,y)$ is in FP if and only if there is a deterministic polynomial time algorithm that, given $x$, can find some $y$ such that $P(x,y)$ holds.

The definition above seems to imply that for all relations in FP it holds that for every $x$ there exists at least one $y$ which its length is polynomial in the length of $x$. However, it does not seem to restrict that there exists more $y$ for that $x$ so that $P(x,y)$ holds while $y$ is exponentially longer than $x$.

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$.

This definition implies that for a relation in FNP it need not to be true that there exists at least one $y$ for every $x$ so that $P(x,y)$ holds. It implies however that if $P(x,y)$ holds, $y$ has to be at most polynomially longer than $x$.

In literature, one can read that FP $\subseteq$ FNP. As far as I do (or do not) understand, this can not be true. It is possible that for some relation $R(x,y) \in$ FP there exists a $(x,y)$ so that $R(x,y)$ holds and $y$ is exponentially longer than $x$. Because of this, this relation does not belong to FNP and therefore FP $\not\subseteq$ FNP.

Are the definitions on Wikipedia incomplete? Am I missing something?

Either way, what are some good sources to read up on function problems (I deem myself knowledgeable of decision problems)?

Answer 1

I found the following in Papadimitriou's book Computational Complexity which I've found satisfying.

Let $R \subseteq \Sigma^* \times \Sigma^*$ be a binary relation on strings.

$R$ is called polynomially decidable if there is a deterministic Turing Machine deciding the language $\{x;y : (x,y) \in R\}$ in polynomial time.

We say that $R$ is polynomially balanced if $(x,y) \in R$ implies $|y| \leq |x|^k$ for some $k \geq 1$.

Then Papadimitriou notes the following, which basically is another definition for NP:

Let $L \subseteq \Sigma^*$ be a language. $L \in$ NP if and only if there is a polynomially decidable and polynomially balanced relation $R$, such that $L = \{x : (x,y) \in R$ for some $y \}$.

A few dozen pages later...

The function problem associated with $L$ [$\in$ NP], denoted $FL$ [here $L$ stands for said language, not logspace], is the following computational problem:

Given $x$, find a string $y$ such that $R_L(x,y)$ if such a string exists; if no such string exists, return "no".

Then

The class of all function problems associated as above with languages in NP is called FNP. FP is the subclass resulting if we only consider function problems in FNP that can be solved in polynomial time.

Answer 2

Let's forget about the Wikipedia definitions and come up with our own.

A function $f$ is in $\mathsf{FP}$ if there is a polytime Turing machine that on input $x$ outputs $f(x)$.

A function $f$ is in $\mathsf{FNP^\ast}$ if:

1. The function $f$ is polynomially bounded: there exists a polynomial $p$ such that $|f(x)| \leq p(|x|)$.

2. There is a polytime Turing machine that given $x,y$ determines whether $f(x)=y$.

If $f$ is in $\mathsf{FP}$ then it is definitely polynomially bounded. Since we can compute $f(x)$ in polynomial time, given $x,y$ we can compute $f(x)$ and compare it to $y$, all in polynomial time.

Consulting the complexity zoo, it seems that $\mathsf{FNP}$ actually has a different definition, and that $\mathsf{FP}$ has two different and incompatible definitions, one of them being the one stated above.

Answer 3

I want to add another set of definitions from Automata, Computability and Complexity by Elaine Rich.

The Class FP: A binary relation $Q$ is in $\mathsf{FP}$ iff there is a deterministic polynomial time algorithm that, given an arbitrary input $x$, can find some $y$ such that $(x,y) \in Q$.

The Class FNP: A binary relation $Q$ is in $\mathsf{FNP}$ iff there is a deterministic polynomial time verifier, given an arbitrary input pair $(x,y)$, determines whether $(x,y) \in Q$. Equivalentely, $Q$ is in $\mathsf{FNP}$ iff there is a nondeterministic polynomial time algorithm that, given an arbitrary input $x$, can find some $y$ such that $(x,y) \in Q$

This is only slightly different than the definitions found on Wikipedia but they imply different things nonetheless. Most importantly, Elaine Rich her definition of $\mathsf{FNP}$ doesn't imply that if $(x,y) \in Q$, $y$ has to be polynomial in $x$. It's likely that the wiki-definitions are sloppy copies of these.

From these definitions it is more clear that $\mathsf{FP} \subseteq \mathsf{TFNP} \subseteq \mathsf{FNP}$.