<p>Consider these two classes of search problems:</p>

<ol>
<li>Search problems with poly-sized solutions s.t. verifying solutions is in <strong>P</strong>.</li>
<li>Search problems with poly-sized solutions s.t. verifying solutions is in <strong>NP</strong>.</li>
</ol>

<p>Class 1 is <strong>FNP</strong>. Is there any commonly used name for class 2?</p>

<hr>

<p>Examples of problems in these classes:</p>

<ol>
<li>Given a graph with <em>n</em> nodes, find a proper 3-coloring.</li>
<li>Given a graph with <em>n</em> nodes, find a partial 3-coloring such that the first <em>n</em>/2 are colored and the partial coloring can be extended to a proper 3-coloring.</li>
</ol>

<p>Note that these two problems are, in essence, equivalent, but the key point is that a solution to problem 2 requires a proof, while a solution to problem 1 is already a proof.</p>

CC BY-SA 4.0
2019-12-09T14:04:32.097Z
It should be in '$F\Sigma_2^P$' however is there a hierarchy?
Turbo
CC BY-SA 4.0
2019-12-09T14:31:01.743Z
In other words, these are just FNP problems composed with a projection. I don’t think there is an established name (even though the concept is quite natural and comes up now and then). It makes no sense to call it $F\Sigma^P_2$, as the latter would denote $\Sigma^P_2$ search problems, that is, with a coNP verifier.
Emil Jeřábek
<cc.complexity-theory><complexity-classes>
Terminology: FNP, with P replaced by NP?
Jukka Suomela
# Terminology: FNP, with P replaced by NP?

(Asked by: username_0 on 2019-12-09)

Consider these two classes of search problems:

1. Search problems with poly-sized solutions s.t. verifying solutions is in **P**.
2. Search problems with poly-sized solutions s.t. verifying solutions is in **NP**.

Class 1 is **FNP**. Is there any commonly used name for class 2?

---

Examples of problems in these classes:

1. Given a graph with *n* nodes, find a proper 3-coloring.
2. Given a graph with *n* nodes, find a partial 3-coloring such that the first *n*/2 are colored and the partial coloring can be extended to a proper 3-coloring.

Note that these two problems are, in essence, equivalent, but the key point is that a solution to problem 2 requires a proof, while a solution to problem 1 is already a proof.

**Tags:** cc.complexity-theory, complexity-classes

> **Comments:**
> **username_1**: It should be in '$F\Sigma_2^P$' however is there a hierarchy?  
> **username_2**: In other words, these are just FNP problems composed with a projection. I don’t think there is an established name (even though the concept is quite natural and comes up now and then). It makes no sense to call it $F\Sigma^P_2$, as the latter would denote $\Sigma^P_2$ search problems, that is, with a coNP verifier.  

---

## 0 answers

