7
$\begingroup$

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)?

$\endgroup$
  • $\begingroup$ Have you looked at any books/sources other than Wikipedia? If you want formal definitions, I wouldn't recommend relying on Wikipedia as your primary source. Instead, a textbook on complexity theory is probably a better choice, or lecture notes from a course (probably graduate course) on complexity theory that covers these topics. $\endgroup$ – D.W. Mar 16 '17 at 20:16
  • $\begingroup$ I'm reading 'Computational Complexity: A Modern Approach' by Arora et. al. but that book doesn't cover function problems. I'm reading articles which define PLS and PPA(D) [Papadimitrou]. Those articles only 'define' them as "function equivalents of (N)P". I can understand PLS and PPA(D), but when I reason about them in depth I always bump into the problem I don't know any good definition of FP and FNP. $\endgroup$ – Auberon Mar 16 '17 at 20:20
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Now to figure out why FP $\subseteq$ TFNP... $\endgroup$ – Auberon Mar 17 '17 at 17:35
  • $\begingroup$ Note that $\mathbf{FP}$ has another, incompatible definition which is also commonly used. $\endgroup$ – Yuval Filmus Mar 17 '17 at 21:48
  • $\begingroup$ @YuvalFilmus In literature it is accepted that FP $\subseteq$ TFNP $\subseteq$ FNP . I'd say whichever definition of FP exists out there that satisfies this is a correct one. Papadimitriou also states the said inclusions in his book. However I do not see how his definition of FP implies it.... $\endgroup$ – Auberon Mar 17 '17 at 22:51
  • $\begingroup$ This depends on which part of the literature you look at. For me FP has always been the class of functions computable in polytime, whereas FNP and TFNP are niche terms used by people working on search problems. $\endgroup$ – Yuval Filmus Mar 17 '17 at 22:58
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I'd argue that FP and FNP aren't sets of functions, but sets of strings. Additionally, functionimplies there's exactly one $y$ for each $x$, which doesn't have to be the case. They are relations. $\endgroup$ – Auberon Mar 17 '17 at 17:04
  • $\begingroup$ You seem to be right about $\mathsf{FNP}$, but $\mathsf{FP}$ has several different (incompatible) definitions. See for example the complexity zoo. $\endgroup$ – Yuval Filmus Mar 17 '17 at 21:42
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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