4
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Emil Jeřábek May 15 '15 at 13:38
  • $\begingroup$ 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? $\endgroup$ – John Threepwood May 15 '15 at 18:29
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – John Threepwood May 22 '15 at 10:13
  • $\begingroup$ 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 . $\endgroup$ – Emil Jeřábek May 24 '15 at 17:48
  • $\begingroup$ 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}$ $\endgroup$ – user6973 Jun 30 '15 at 4:38
  • $\begingroup$ See the references in the complexity zoo. The basic idea is to find the number of positively answered oracle queries by binary search. $\endgroup$ – Emil Jeřábek Jun 30 '15 at 8:33

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.