patternMinor
Function problems and $FP \subseteq FNP$
Viewed 0 times
subseteqfnpfunctionandproblems
Problem
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)?
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)?
Solution
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.
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.
Context
StackExchange Computer Science Q#71617, answer score: 4
Revisions (0)
No revisions yet.