<p>$\let\mr\mathrm\def\xx{\mr{FP^{NP[wit,\log]}}}\xx$ is not defined as a class of <em>functions</em>, but of potentially multivalued <em>search</em> <em>problems</em>. It is not difficult to construct $\xx$-complete search problems by variating the usual Cook–Levin theorem. Here is one, somewhat simplified from what I suggested in the comment above.</p>

<p>First, as should be mentioned somewhere in the BKT paper, the class $\xx$ does not change if all the oracle queries are made to ordinary, nonwitnessing NP oracles, except for the final query, which is guaranteed to succeed, and returns a witness $(u,v)$ such that $u$ is the output of the algorithm. Moreover, since $\mr{P^{NP[\log]}}=\mr{P^{\|NP}}$, we can simulate the initial $O(\log n)$ nonwitnessing queries with polynomially many <em>nonadaptive</em> (parallel) NP queries.</p>

<p>Now, if $A(x)$ is a polynomial-time algorithm making $n^c$ nonadaptive queries to an NP-oracle, and one witnessing query in the fashion described above, then</p>

<p>$\qquad B(x,1^j)\iff{}$ “the $j$th parallel query made by $A$ on input $x$ is true”</p>

<p>is an NP-predicate, hence by the Cook–Levin theorem, it is equivalent to the satisfiability of a poly-time (or log-space) constructible 3-CNF. Likewise,</p>

<p>$\qquad C(x,a_1,\dots,a_{n^c})\iff{}$ “the final query is true in the run of $A$ on input $x$ such that the $j$th parallel query is answered with $a_j\in\{0,1\}$ for each $j$”</p>

<p>is an NP-predicate, and the output of $A(x)$ can be read off from a witness to $C(x,\vec a)$ if supplied with the correct $\vec a$. Again, it can be expressed as a 3-CNF. Thus, the following search problem is $\xx$-complete:</p>

<blockquote>
  <p><strong>Input:</strong> A sequence of 3-CNFs $(\phi_1,\dots,\phi_n)$ (in whatever variables), and a 3-CNF $\psi(x_1,\dots,x_n,y_1,\dots,y_m)$</p>
  
  <p><strong>Output:</strong> A satisfying assignment $(b_1,\dots,b_m)$ to $\psi(a_1,\dots,a_n,y_1,\dots,y_m)$, where
  $$a_j=\begin{cases}1&amp;\text{if $\phi_j$ is satisfiable,}\\
0&amp;\text{otherwise.}\end{cases}$$</p>
</blockquote>

<hr>

<p>Perhaps a more compelling $\xx$-complete problem is the following search variant of MAX-3SAT:</p>

<blockquote>
  <p><strong>Input:</strong> A 3-CNF $\phi$.</p>
  
  <p><strong>Output:</strong> An assignment that satisfies the maximum possible number of clauses in $\phi$.</p>
</blockquote>

<p>To see that this works, let $(\phi_1,\dots,\phi_n)$ and $\psi$ be as in the previous problem, where due to the way the reduction works, we may assume that $\psi(a_1,\dots,a_n,\vec y)$ is satisfiable for every $\vec a\in\{0,1\}^n$. We may also assume that variables used by the $\phi_j$ are pairwise disjoint, and disjoint from $\vec x,\vec y$. Then let $\phi$ be the conjunction of all clauses of $\phi_1,\dots,\phi_n,\psi$, together with a handful additional clauses that express that $x_j$ is true iff all clauses of $\phi_j$ are true.</p>

<p>Given any assignment to variables of $\phi_1,\dots,\phi_n$, we can find an assignment of the remaining variables that satisfies all clauses of $\psi$, and the additional clauses. Moreover, we can change an assignment of the variables of $\phi_j$ without affecting $\phi_k$ for $k\ne j$.</p>

<p>Thus, an assignment satisfying the maximal number of clauses of $\phi$ will also individually maximize the number of satisfied clauses of each $\phi_j$, and in particular, it will satisfy the whole $\phi_j$ iff $\phi_j$ is satisfiable, and its restriction to the $\vec y$ variables will be a correct solution to the original problem.</p>

<hr>

<p>The above are multivalued search problems. As far as I am aware, it is an open problem whether there are $\xx$-complete functions.</p>

<p>As should also be mentioned in the BKT paper, predicates (i.e., $\{0,1\}$-valued functions) in $\xx$ are computable using nonwitnessing oracles: they are exactly the predicates in the class
$$\Theta_2^{\mr P}=\mr{P^{NP[\log]}}=\mr{P^{\|NP}}=\mr{L^{NP}}.$$
Consequently, a function $f$ is in $\xx$ if and only if</p>

<ul>
<li><p>$|f(x)|$ is polynomially bounded in $|x|$, and</p></li>
<li><p>the bit-graph of $f$ is in $\Theta_2^\mr P$.</p></li>
</ul>

<p>Thus, we could call the class of such functions $\mr{F\Theta_2^P}$. A similar reasoning as above shows that the following is an $\mr{F\Theta_2^P}$-complete function:</p>

<blockquote>
  <p><strong>Input:</strong> A sequence of 3-CNFs $(\phi_1,\dots,\phi_n)$</p>
  
  <p><strong>Output:</strong> The sequence $(a_1,\dots,a_n)$, where
  $$a_j=\begin{cases}1&amp;\text{if $\phi_j$ is satisfiable,}\\
0&amp;\text{otherwise.}\end{cases}$$</p>
</blockquote>

<p>Since $\mr{F\Theta_2^P}$ is closed under composition, an inspection of the two complete problems shows:</p>

<blockquote>
  <p><strong>Proposition:</strong> The following are equivalent.</p>
  
  <ol>
  <li><p>There exists an $\xx$-complete function.</p></li>
  <li><p>For every $\xx$-search problem $S(x,y)$, there is an $\mr{F\Theta_2^P}$-function $f$ such that $S(x,f(x))$.</p></li>
  <li><p>There is an $\mr{F\Theta_2^P}$-function that computes a satisfying assignment to any given satisfiable 3-CNF.</p></li>
  </ol>
</blockquote>

CC BY-SA 3.0
2015-05-22T10:13:54.687Z
Outstanding great answer, thank you very much. It will take me some time to understand it in detail. I often wonder if you come up with all this by yourself or do you have good references. For example for the result of the MAX-3SAT variant?
John Threepwood
CC BY-SA 3.0
2015-05-24T17:48:41.113Z
Yes, I came up with that myself, except for the equivalent description of the class which is given in BKT, and the standard equivalent characterizations of $\Theta^P_2$ for which references can be found e.g. in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pnplog .
Emil Jeřábek
CC BY-SA 3.0
2015-06-30T08:33:36.257Z
See the references in the complexity zoo. The basic idea is to find the number of positively answered oracle queries by binary search.
Emil Jeřábek
CC BY-SA 3.0
2015-05-16T13:51:45.733Z
2015-05-16T16:55:08.490Z
2015-05-16T16:55:08.490Z
Emil Jeřábek
<p>The usage of an $\mathrm{NP}$-oracles which delivers a witness has been proposed for example in [Buss1995]. I would like to see an example of an $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard problem. Can someone tell me?</p>

<p>Since I am not a complexity theory expert, I could not come up with an example nor could I find an example by searching through papers.</p>

<p>References:</p>

<p>[Buss1995] Buss, Krajíček, Takeuti, "Provably total functions in the bounded arithmetic theories $R_3^i$, $U_2^i$ and $V_2^i$" (1995)</p>

CC BY-SA 3.0
2015-05-15T13:38:52.980Z
It’s not difficult to cook up $\mathrm{FP^{NP[wit,\log]}}$-complete *search* *problems*: e.g., evaluation of constant circuits with witnessing SAT oracle gates. However, this is an inherently multivalued problem. I don’t think it is known if there are $\mathrm{FP^{NP[wit,\log]}}$-complete (single-valued) *functions*.
Emil Jeřábek
CC BY-SA 3.0
2015-05-15T18:29:54.757Z
Thank you Emil Jeřábek. What exactly do you mean by 'evaluation of constant circuits with witnessing SAT oracle gates'? Can you refer to a paper where I can further read about it?
John Threepwood
<np-hardness><complexity-classes>
Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard?
John Threepwood
# Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard?

(Asked by: username_0 on 2015-05-14)

The usage of an $\mathrm{NP}$-oracles which delivers a witness has been proposed for example in [Buss1995]. I would like to see an example of an $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard problem. Can someone tell me?

Since I am not a complexity theory expert, I could not come up with an example nor could I find an example by searching through papers.

References:

[Buss1995] Buss, Krajíček, Takeuti, "Provably total functions in the bounded arithmetic theories $R\_3^i$, $U\_2^i$ and $V\_2^i$" (1995)

**Tags:** np-hardness, complexity-classes
> **Comments:**
> **username_1**: It’s not difficult to cook up $\mathrm{FP^{NP[wit,\log]}}$-complete *search* *problems*: e.g., evaluation of constant circuits with witnessing SAT oracle gates. However, this is an inherently multivalued problem. I don’t think it is known if there are $\mathrm{FP^{NP[wit,\log]}}$-complete (single-valued) *functions*.  
> **username_0**: Thank you Emil Jeřábek. What exactly do you mean by 'evaluation of constant circuits with witnessing SAT oracle gates'? Can you refer to a paper where I can further read about it?  

---

## 1 answers

### Answer by username_1 on 2015-05-16. Score: 3

$\let\mr\mathrm\def\xx{\mr{FP^{NP[wit,\log]}}}\xx$ is not defined as a class of *functions*, but of potentially multivalued *search* *problems*. It is not difficult to construct $\xx$-complete search problems by variating the usual Cook–Levin theorem. Here is one, somewhat simplified from what I suggested in the comment above.

First, as should be mentioned somewhere in the BKT paper, the class $\xx$ does not change if all the oracle queries are made to ordinary, nonwitnessing NP oracles, except for the final query, which is guaranteed to succeed, and returns a witness $(u,v)$ such that $u$ is the output of the algorithm. Moreover, since $\mr{P^{NP[\log]}}=\mr{P^{\|NP}}$, we can simulate the initial $O(\log n)$ nonwitnessing queries with polynomially many *nonadaptive* (parallel) NP queries.

Now, if $A(x)$ is a polynomial-time algorithm making $n^c$ nonadaptive queries to an NP-oracle, and one witnessing query in the fashion described above, then

$\qquad B(x,1^j)\iff{}$ “the $j$th parallel query made by $A$ on input $x$ is true”

is an NP-predicate, hence by the Cook–Levin theorem, it is equivalent to the satisfiability of a poly-time (or log-space) constructible 3-CNF. Likewise,

$\qquad C(x,a\_1,\dots,a\_{n^c})\iff{}$ “the final query is true in the run of $A$ on input $x$ such that the $j$th parallel query is answered with $a\_j\in\{0,1\}$ for each $j$”

is an NP-predicate, and the output of $A(x)$ can be read off from a witness to $C(x,\vec a)$ if supplied with the correct $\vec a$. Again, it can be expressed as a 3-CNF. Thus, the following search problem is $\xx$-complete:

> **Input:** A sequence of 3-CNFs $(\phi\_1,\dots,\phi\_n)$ (in whatever variables), and a 3-CNF $\psi(x\_1,\dots,x\_n,y\_1,\dots,y\_m)$
>
> **Output:** A satisfying assignment $(b\_1,\dots,b\_m)$ to $\psi(a\_1,\dots,a\_n,y\_1,\dots,y\_m)$, where
> $$a\_j=\begin{cases}1&\text{if $\phi\_j$ is satisfiable,}\\
> 0&\text{otherwise.}\end{cases}$$

---

Perhaps a more compelling $\xx$-complete problem is the following search variant of MAX-3SAT:

> **Input:** A 3-CNF $\phi$.
>
> **Output:** An assignment that satisfies the maximum possible number of clauses in $\phi$.

To see that this works, let $(\phi\_1,\dots,\phi\_n)$ and $\psi$ be as in the previous problem, where due to the way the reduction works, we may assume that $\psi(a\_1,\dots,a\_n,\vec y)$ is satisfiable for every $\vec a\in\{0,1\}^n$. We may also assume that variables used by the $\phi\_j$ are pairwise disjoint, and disjoint from $\vec x,\vec y$. Then let $\phi$ be the conjunction of all clauses of $\phi\_1,\dots,\phi\_n,\psi$, together with a handful additional clauses that express that $x\_j$ is true iff all clauses of $\phi\_j$ are true.

Given any assignment to variables of $\phi\_1,\dots,\phi\_n$, we can find an assignment of the remaining variables that satisfies all clauses of $\psi$, and the additional clauses. Moreover, we can change an assignment of the variables of $\phi\_j$ without affecting $\phi\_k$ for $k\ne j$.

Thus, an assignment satisfying the maximal number of clauses of $\phi$ will also individually maximize the number of satisfied clauses of each $\phi\_j$, and in particular, it will satisfy the whole $\phi\_j$ iff $\phi\_j$ is satisfiable, and its restriction to the $\vec y$ variables will be a correct solution to the original problem.

---

The above are multivalued search problems. As far as I am aware, it is an open problem whether there are $\xx$-complete functions.

As should also be mentioned in the BKT paper, predicates (i.e., $\{0,1\}$-valued functions) in $\xx$ are computable using nonwitnessing oracles: they are exactly the predicates in the class
$$\Theta\_2^{\mr P}=\mr{P^{NP[\log]}}=\mr{P^{\|NP}}=\mr{L^{NP}}.$$
Consequently, a function $f$ is in $\xx$ if and only if

* $|f(x)|$ is polynomially bounded in $|x|$, and
* the bit-graph of $f$ is in $\Theta\_2^\mr P$.

Thus, we could call the class of such functions $\mr{F\Theta\_2^P}$. A similar reasoning as above shows that the following is an $\mr{F\Theta\_2^P}$-complete function:

> **Input:** A sequence of 3-CNFs $(\phi\_1,\dots,\phi\_n)$
>
> **Output:** The sequence $(a\_1,\dots,a\_n)$, where
> $$a\_j=\begin{cases}1&\text{if $\phi\_j$ is satisfiable,}\\
> 0&\text{otherwise.}\end{cases}$$

Since $\mr{F\Theta\_2^P}$ is closed under composition, an inspection of the two complete problems shows:

> **Proposition:** The following are equivalent.
>
> 1. There exists an $\xx$-complete function.
> 2. For every $\xx$-search problem $S(x,y)$, there is an $\mr{F\Theta\_2^P}$-function $f$ such that $S(x,f(x))$.
> 3. There is an $\mr{F\Theta\_2^P}$-function that computes a satisfying assignment to any given satisfiable 3-CNF.

> **Comments:**
> **username_0**: Outstanding great answer, thank you very much. It will take me some time to understand it in detail. I often wonder if you come up with all this by yourself or do you have good references. For example for the result of the MAX-3SAT variant?  
> **username_1**: Yes, I came up with that myself, except for the equivalent description of the class which is given in BKT, and the standard equivalent characterizations of $\Theta^P_2$ for which references can be found e.g. in https://complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pnplog .  
> **username_1**: See the references in the complexity zoo. The basic idea is to find the number of positively answered oracle queries by binary search.  

---

