12
$\begingroup$

In his book Computational Complexity, Papadimitriou defines FNP as follows:

Suppose that $L$ is a language in NP. By Proposition 9.1, there is a polynomial-time decidable, polynomially balanced relation $R_L$ such that for all strings $x$: There is a string $y$ with $R_L(x,y)$ if and only if $x\in L$. The function problem associated with $L$, denoted $FL$, 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".

The class of all function problems associated as above with language 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.

(...)

(...), we call a problem $R$ in FNP total if for every string $x$ there is at least one $y$ such that $R(x,y)$. The subclass of FNP containing all total function problems is denoted TFNP.

In a venn diagram in the chapter overview, Papadimitriou implies that FP $\subseteq$ TFNP $\subseteq$ FNP.

I have a hard time understanding why exactly it holds that FP $\subseteq$ TFNP since problems in FP do not have to be total per se.

To gain a better understanding, I've been plowing through literature to find a waterproof definition of FP,FNP and sorts, without success.

In my very (humble) opinion, I think there is little (correct!) didactic material of these topics.

For decision problems, the classes are sets of languages (i.e. sets of strings).

What exactly are the classes for function problems? Are they sets of relations, languages, ... ? What is a solid definition?

$\endgroup$
  • 4
    $\begingroup$ The common notation is somewhat sloppy. First, FP was and is used to denote the class of poly-time functions (hence total) outside the context of NP search problems, where it has been redefined. Second, every search problem solvable in polynomial time has a total extension solvable in polynomial time, so in that sense, there is not much real difference between a total and non-total definition of FP, so the two are conflated by abuse of language. $\endgroup$ – Emil Jeřábek supports Monica Mar 21 '17 at 15:56
10
$\begingroup$

Emil Jerabek's comment is a nice summary, but I wanted to point out that there are other classes with clearer definitions that capture more-or-less the same concept, and to clarify the relation between all these things.

[Warning: while I believe I've gotten the definitions right, some of the things below reflect my personal preferences - I've tried to be clear about where that was.]

In the deterministic world, a function class is just a collection of functions (in the usual, mathematical sense of the word "function", that is, a map $\Sigma^* \to \Sigma^*$). Occasionally we want to allow "partial functions," whose output is "undefined" for certain inputs. (Equivalently, functions that are defined on a subset of $\Sigma^*$ rather than all of it.)

Unfortunately, there are two different definitions for $\mathsf{FP}$ floating around, and as far as I can tell they are not equivalent (though they are "morally" equivalent).

  • $\mathsf{FP}$ (definition 1) is the class of functions that can be computed in polynomial-time. Whenever you see $\mathsf{FP}$ and its not in a context where people are talking about $\mathsf{FNP}, \mathsf{TFNP}$, this is the definition I assume.

In the nondeterministic world things get a little funny. There, it is convenient to allow "partial, multi-valued functions." It would be natural to also call such a thing a binary relation, that is, a subset of $\Sigma^* \times \Sigma^*$. But from the complexity point of view it is often philosophically and mentally useful to think of these things as "nondeterministic functions." I think many of these definitions are clarified by the following classes (whose definitions are completely standardized, if not very well-known):

  • $\mathsf{NPMV}$: The class of "partial, multi-valued functions" computable by a nondeterministic machine in polynomial time. What this means is there is a poly-time nondeterministic machine, and on input $x$, on each nondeterministic branch it may choose to accept and make some output, or reject and make no output. The "multi-valued" output on input $x$ is then the set of all outputs on all nondeterministic branches when given $x$ as input. Note that this set can be empty, so as a "multi-valued function" this may only be partial. If we think of it in terms of binary relations, this corresponds to the relation $\{(x,y) : y \text{ is output by some branch of the computation on input } x\}$.

  • $\mathsf{NPMV}_t$: Total "functions" in $\mathsf{NPMV}$, that is, on every input $x$, at least one branch accepts (and therefore makes an output, by definition)

  • $\mathsf{NPSV}$: Single-valued (potentially partial) functions in $\mathsf{NPMV}$. There is some flexibility here, however, in that multiple branches may accept, but if any branch accepts, then all accepting branches must be guaranteed to make the same output (so that it really is single-valued). However, it is still possible that no branch accepts, so the function is only a "partial function" (i.e. not defined on all of $\Sigma^*$).

  • $\mathsf{NPSV}_t$: Single-valued total functions in $\mathsf{NPSV}$. These really are functions, in the usual sense of the word, $\Sigma^* \to \Sigma^*$. It is a not-too-hard exercise to see that $\mathsf{NPSV}_t = \mathsf{FP}^{\mathsf{NP} \cap \mathsf{coNP}}$ (using Def 1 for FP above).

When we talk about potentially multi-valued functions, talking about containment of complexity classes isn't really useful any more: $\mathsf{NPMV} \not\subseteq \mathsf{NPSV}$ unconditionally simply because $\mathsf{NPSV}$ doesn't contain any multi-valued "functions", but $\mathsf{NPMV}$ does. Instead, we talk about "c-containment", denoted $\subseteq_c$. A (potentially partial, multi-valued) function $f$ refines a (potentially partial multi-valued) function $g$ if: (1) for every input $x$ for which $g$ makes some output, so does $f$, and (2) the outputs of $f$ are always a subset of the outputs of $g$. The proper question is then whether every $\mathsf{NPMV}$ "function" has an $\mathsf{NPSV}$ refinement. If so, we write $\mathsf{NPMV} \subseteq_c \mathsf{NPSV}$.

  • $\mathsf{PF}$ (a little less standard) is the class of (potentially partial) functions computable in poly-time. That is, a function $f\colon D \to \Sigma^*$ ($D \subseteq \Sigma^*$) is in $\mathsf{PF}$ if there is a poly-time deterministic machine such that, on inputs $x \in D$ the machine outputs $f(x)$, and on inputs $x \notin D$ the machine makes no output (/rejects/says "no"/however you want to phrase it).

  • $\mathsf{FNP}$ is a class of "function problems" (rather than a class of functions). I would also call $\mathsf{FNP}$ a "relational class", but really whatever words you use to describe it you need to clarify yourself afterwards, which is why I'm not particularly partial to this definition. To any binary relation $R \subseteq \Sigma^* \times \Sigma^*$ there is an associated "function problem." What is a function problem? I don't have a clean mathematical definition the way I do for language/function/relation; rather, it's defined by what a valid solution is: a valid solution to the function problem associated to $R$ is any (potentially partial) function $f$ such that if $(\exists y)[R(x,y)]$ then $f$ outputs any such $y$, and otherwise $f$ makes no output. $\mathsf{FNP}$ is the class of function problems associated to relations $R$ such that $R \in \mathsf{P}$ (when considered as a language of pairs) and is p-balanced. So $\mathsf{FNP}$ is not a class of functions, nor a class of languages, but a class of "function problems," where "problem" here is defined roughly in terms of what it means to solve it.

  • $\mathsf{TFNP}$ is then the class of function problems in $\mathsf{FNP}$ - defined by a relation $R$ as above - such $R$ is total, in the sense that for every $x$ there exists a $y$ such that $R(x,y)$.

In order to not have to write things like "If every $\mathsf{FNP}$ (resp., $\mathsf{TFNP}$) function problem has a solution in $\mathsf{PF}$ (resp., $\mathsf{FP}$ according to above definition), then..." in this context one uses Definition 2 of $\mathsf{FP}$, which is:

  • $\mathsf{FP}$ (definition 2) is the class of function problems in $\mathsf{FNP}$ which have a poly-time solution. One can assume that the solution (=function) here is total by picking a special string $y_0$ that is not a valid $y$ for any $x$, and having the function output $y_0$ when there would otherwise be no valid $y$. (If needed, we can modify the relation $R$ by prepending every $y$ with a 1, and then take $y_0$ to be the string 0; this doesn't change the complexity of anything involved).

Here's how these various definitions relate to one another, $\mathsf{FNP} \subseteq \mathsf{FP}$ (definition 2, which is what you should assume because it's in a context where it's being compared with $\mathsf{FNP}$) is equivalent to $\mathsf{NPMV} \subseteq_c \mathsf{PF}$. $\mathsf{TFNP} \subseteq \mathsf{FP}$ (def 2) is equivalent to $\mathsf{NPMV}_t \subseteq_c \mathsf{FP}$ (def 1).

$\endgroup$
  • $\begingroup$ Thank you for your extensive answer. I'm trying to digest it and it has been very helpful so far. I assume, however, you meant FP $\subseteq$ FNP and FP $\subseteq$ TFNP in the last paragraph? $\endgroup$ – Auberon Mar 23 '17 at 11:36
  • 1
    $\begingroup$ @Auberon: No, the last paragraph is translating between various conjectures. It says that $\mathsf{FNP} \subseteq \mathsf{FP} \Leftrightarrow \mathsf{NPMV} \subseteq_c \mathsf{PF}$, etc. $\endgroup$ – Joshua Grochow Mar 23 '17 at 16:28
  • $\begingroup$ @JoshuaGrochow $NP\in P^{TFNP}$ or $NP\in P^{UP}$ possible or the hierarchy collapses? Also does $P^{UP}$ in $P^{TFNP}$ or vice versa hold (it seems plausible as there seem no implication either way)? $\endgroup$ – T.... May 26 at 15:07
3
$\begingroup$

In addition to Joshua's extensive answer, I want to add the following definitions from Elaine Ruch her Automata, Computability and Complexity.

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$

From these definitions it is clear that $\mathsf{FP} \subseteq \mathsf{TFNP} \subseteq \mathsf{FNP}$. She also briefly talks about problems outside of $\mathsf{FNP}$.

For me, this has been the most satisfying resource that consists out of one single page I've found since a long time.

$\endgroup$
  • $\begingroup$ After I have given these definition some thought, I suspect that the two 'equivalent' definitions of $\mathsf{FNP}$ aren't equivalent at all... $\endgroup$ – Auberon Mar 28 '17 at 17:02
  • $\begingroup$ I think to get equivalence one needs to assume the relation is p-bounded (that is, there is a polynomial $p$ such that if $\exists y$ such that $(x,y) \in Q$, then there is such a $y$ with $|y| \leq p(|x|)$). Also, one has to specify what it means for a "nondeterministic algorithm to find a $y$" - that is, what does it mean for a nondeterministic algorithm to "make an output"? This is part of why I like the NPMV family of definitions... $\endgroup$ – Joshua Grochow Jul 3 '18 at 22:35

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.