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)
$\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&amp;\text{if $\phi_j$ is satisfiable,}\\
0&amp;\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&amp;\text{if $\phi_j$ is satisfiable,}\\
0&amp;\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.
  
  
  There exists an $\xx$-complete function.
  For every $\xx$-search problem $S(x,y)$, there is an $\mr{F\Theta_2^P}$-function $f$ such that $S(x,f(x))$.
  There is an $\mr{F\Theta_2^P}$-function that computes a satisfying assignment to any given satisfiable 3-CNF.