<p>I hope this isn't a dumb question, but I've been driving myself nuts regarding the following.</p>
<p>The definition of <span class="math-container">$\mathsf{FNP}$</span> that I've found in many places is the following:
A relation <span class="math-container">$R(x,y)$</span> is in <span class="math-container">$\mathsf{FNP}$</span> if (1) <span class="math-container">$|y|$</span> is polynomially bounded in <span class="math-container">$|x|$</span>; and (2) there is a polynomial-time Turing machine <span class="math-container">$M$</span> that outputs <span class="math-container">$1$</span> on input <span class="math-container">$(x,y)$</span> if and only if <span class="math-container">$R(x,y)$</span> holds.</p>
<p>Such a relation implicitly defines a computational search problem <span class="math-container">$P$</span> in which the input is <span class="math-container">$x$</span> and the goal is to find <span class="math-container">$y$</span> such that <span class="math-container">$R(x,y)$</span> holds, if such a <span class="math-container">$y$</span> exists.</p>
<p>This makes some sense. E.g., it's clear that <span class="math-container">$\mathsf{FSAT}$</span> is in <span class="math-container">$\mathsf{FNP}$</span> from this definition, and it's relatively easy to show that it's also <span class="math-container">$\mathsf{FNP}$</span>-hard. More generally, there's a nice one-to-one correspondence between <span class="math-container">$\mathsf{FNP}$</span> relations and <span class="math-container">$\mathsf{NP}$</span> decision problems with this definition.</p>
<p>However, this definition seems strange when you consider that it doesn't actually seem to be closed under <em>relaxation</em>. In other words, there are relations <span class="math-container">$R$</span> and <span class="math-container">$R'$</span> such that <span class="math-container">$R(x,y) \implies R'(x,y)$</span> and <span class="math-container">$R \in \mathsf{FNP}$</span>, but <span class="math-container">$R' \notin \mathsf{FNP}$</span>. This seems rather silly, because in some sense <span class="math-container">$R'$</span> defines a search problem <span class="math-container">$P'$</span> that can't possibly be harder than the search problem <span class="math-container">$P$</span> defined by <span class="math-container">$R$</span> (since every solution to <span class="math-container">$P$</span> is also a solution to <span class="math-container">$P'$</span>).</p>
<p>For example, let <span class="math-container">$R$</span> be the relation <span class="math-container">$R(\mathcal{C},y)$</span> corresponding to <span class="math-container">$\mathsf{FSAT}$</span> that holds when <span class="math-container">$\mathcal{C}(y) = 1$</span>, where we interpret <span class="math-container">$\mathcal{C}$</span> as a circuit with one-bit output. Then, we can take <span class="math-container">$R'$</span> to be the relation that holds <em>either</em> when <span class="math-container">$R(\mathcal{C},y)$</span> holds <em>or</em> when, say, <span class="math-container">$\mathcal{C}$</span> is a circuit that solves the halting problem. <span class="math-container">$R$</span> is clearly an <span class="math-container">$\mathsf{FNP}$</span> relation (and even <span class="math-container">$\mathsf{FNP}$</span>-complete), but <span class="math-container">$R'$</span> is provably undecidable. However, of course, the corresponding search problem for <span class="math-container">$R'$</span> cannot be harder than the corresponding search problem for <span class="math-container">$R$</span>.</p>
<p>Is this an intentional feature of the definition of <span class="math-container">$\mathsf{FNP}$</span>, and if so why? Are there alternative definitions that are closed under relaxation?</p>

CC BY-SA 4.0
2023-08-15T17:06:51.827Z
Intentional or not, FNP is not closed under relaxation. Worse yet, it is not closed under projection.
Emil Jeřábek
CC BY-SA 4.0
2023-08-15T17:17:29.533Z
Hi @EmilJeřábek. Thanks for the response! Can I ask what projection means?
Noah Stephens-Davidowitz
CC BY-SA 4.0
2023-08-15T17:38:34.433Z
I just mean that if $R$ is an FNP problem $x\mapsto(y_0,y_1)$ whose values are pairs, then the corresponding problem $x\mapsto y_0$ where we drop one of the components is not necessarily in FNP. In particular, the set of FNP problems is not closed under composition, which is something one usual wants from a well-behaved class of (multi-)functions.
Emil Jeřábek
CC BY-SA 4.0
2023-08-15T18:34:31.343Z
Ah, I see. That makes sense. Thanks!
Noah Stephens-Davidowitz
CC BY-SA 4.0
2023-08-21T05:26:11.043Z
@EmilJeřábek A nitpick:  FNP is not closed under projection unless P=NP.
Dmytro Taranovsky
<complexity><search-problem>
How is FNP defined? Or, is FNP closed under relaxation?
Noah Stephens-Davidowitz
# How is FNP defined? Or, is FNP closed under relaxation?

(Asked by: username_0 on 2023-08-15)

I hope this isn't a dumb question, but I've been driving myself nuts regarding the following.

The definition of $\mathsf{FNP}$ that I've found in many places is the following:
A relation $R(x,y)$ is in $\mathsf{FNP}$ if (1) $|y|$ is polynomially bounded in $|x|$; and (2) there is a polynomial-time Turing machine $M$ that outputs $1$ on input $(x,y)$ if and only if $R(x,y)$ holds.

Such a relation implicitly defines a computational search problem $P$ in which the input is $x$ and the goal is to find $y$ such that $R(x,y)$ holds, if such a $y$ exists.

This makes some sense. E.g., it's clear that $\mathsf{FSAT}$ is in $\mathsf{FNP}$ from this definition, and it's relatively easy to show that it's also $\mathsf{FNP}$-hard. More generally, there's a nice one-to-one correspondence between $\mathsf{FNP}$ relations and $\mathsf{NP}$ decision problems with this definition.

However, this definition seems strange when you consider that it doesn't actually seem to be closed under *relaxation*. In other words, there are relations $R$ and $R'$ such that $R(x,y) \implies R'(x,y)$ and $R \in \mathsf{FNP}$, but $R' \notin \mathsf{FNP}$. This seems rather silly, because in some sense $R'$ defines a search problem $P'$ that can't possibly be harder than the search problem $P$ defined by $R$ (since every solution to $P$ is also a solution to $P'$).

For example, let $R$ be the relation $R(\mathcal{C},y)$ corresponding to $\mathsf{FSAT}$ that holds when $\mathcal{C}(y) = 1$, where we interpret $\mathcal{C}$ as a circuit with one-bit output. Then, we can take $R'$ to be the relation that holds *either* when $R(\mathcal{C},y)$ holds *or* when, say, $\mathcal{C}$ is a circuit that solves the halting problem. $R$ is clearly an $\mathsf{FNP}$ relation (and even $\mathsf{FNP}$-complete), but $R'$ is provably undecidable. However, of course, the corresponding search problem for $R'$ cannot be harder than the corresponding search problem for $R$.

Is this an intentional feature of the definition of $\mathsf{FNP}$, and if so why? Are there alternative definitions that are closed under relaxation?

**Tags:** complexity, search-problem
> **Comments:**
> **username_1**: Intentional or not, FNP is not closed under relaxation. Worse yet, it is not closed under projection.  
> **username_0**: Hi @EmilJeřábek. Thanks for the response! Can I ask what projection means?  
> **username_1**: I just mean that if $R$ is an FNP problem $x\mapsto(y_0,y_1)$ whose values are pairs, then the corresponding problem $x\mapsto y_0$ where we drop one of the components is not necessarily in FNP. In particular, the set of FNP problems is not closed under composition, which is something one usual wants from a well-behaved class of (multi-)functions.  
> **username_0**: Ah, I see. That makes sense. Thanks!  
> **username_2**: @EmilJeřábek A nitpick:  FNP is not closed under projection unless P=NP.  

---

## 0 answers

