# Tagged Questions

The tag has no usage guidance.

105 views

### Linear Time Hierarchy and Circuit complexity

By Karp-Lipton Theorem we have: $$PH\subseteq P/poly\Rightarrow PH=\Sigma^p_2$$ So this theorem suggest it is unlikely that $PH\subseteq P/poly$. I want to know is there any similar conditional or ...
253 views

179 views

98 views

### Variant of Toda's theorem for intermediate levels of the polynomial hierarchy

Is there a version of Toda's theorem for intermediate levels of the polynomial hierarchy ? More precisely, is there any variant of the Toda's theorem that states: Let $\# wSAT$ be the number of ...
103 views

195 views

### PH and Optimization Problems

If we have a machine which can solve any problem in the second level of PH, can this machine solve optimization problems which is generalized version of NP-complete problems such as MAX-CLIQUE or MIN-...
377 views

### Do good PCPs for NP give us good PCPs for the entire polynomial hierarchy?

The PCP Theorem states that every decision problem in NP has probabilistically checkable proofs (or equivalently, that there exists a complete and quasi-sound proof system for theorems in NP using ...
397 views

217 views

### Complexity of a certain leaf language with Prime & Composite number of accepting paths.

Given a non-deterministic Turing Machine that runs in polynomial time, it accepts if the number of accepting paths are composite, it rejects if the number of accepting paths are prime and it outputs I ...
477 views

### canonical complete problems for $\Delta^P_n$

Finding whether or not a QBF can be satisfied is a canonical complete problem for both $\Sigma^P_n$ (start from $\exists$) and $\Pi^P_n$ (start from $\forall$). What is the canonical complete problem ...
### Is $PH \subseteq PP$?
We know that the first level of the polynomial hierarchy (i.e. NP and co-NP) is in PP, and that $PP \subseteq PSPACE$. We also know from Toda's Theorem that $PH \subseteq P^{PP}$. Do we know whether \$...