5
$\begingroup$

I'm trying to figure out some consequences of the fact that Toda's Theorem relativizes. The (un-relativized) Toda's theorem states that $PH \subset P^{\#P}$ so that for any constant $k$ and any polynomial-time computable function $g: \{0,1\}^{n \times 2k} \to \{0,1\}$ we have that the problem of computing $$\min_{x_1} \max_{y_1} ... \min_{x_k} \max_{y_k} g(x_1,y_1,...,x_k,y_k)$$

can be reduced to the problem of computing $$h(\#\phi)$$ for some polynomial time function $h: \mathbb{N} \to \{0,1\}$ and some polynomial time boolean formula $\phi: \{0,1\}^{poly(n)} \to \{0,1\}$

My question is, do I need to assume that $\phi$ and $g$ can be computed in polynomial time? My conjecture is that since Toda's theorem relativizes, I can assume that they are arbitrary black-box functions and the theorem will still hold.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.