# Example of a function problem which is $\mathrm{FP}^{\mathrm{NP}}[wit, log]$-hard?

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)

• 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 May 15 '15 at 13:38
• 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 May 15 '15 at 18:29

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

• 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 May 22 '15 at 10:13
• 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 complexityzoo.uwaterloo.ca/Complexity_Zoo:P#pnplog . – Emil Jeřábek May 24 '15 at 17:48
• I see why $\: \operatorname{P}^{\hspace{.03 in}\operatorname{NP}[\log]} \hspace{-0.04 in} \subseteq \operatorname{P}^{\hspace{.04 in}||\operatorname{NP}} \;$. $\;\;\;$ Why does the other containment hold? $\hspace{1.84 in}$ – user6973 Jun 30 '15 at 4:38
• 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 Jun 30 '15 at 8:33