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.


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.