# Questions tagged [polynomial-hierarchy]

The tag has no usage guidance.

67 questions
Filter by
Sorted by
Tagged with
335 views

### Structural Complexity Theory References

I'm a PhD student in mathematics (mostly studying algebraic geometry), but I've always been interested in computational complexity theory. As an undergraduate, I completed an independent reading ...
• 113
84 views

### (Where) is determining the mixing time of an implicitly defined graph in the polynomial hierarchy?

Consider an implicitly defined graph; for example, let $G$ be a finite group generated with $n$ generators as $\langle g_1,g_2,\ldots g_n\rangle$ and let $\Gamma$ be the Cayley graph of $G$ under ...
• 1,063
1 vote
82 views

• 12.8k
297 views

### What does $\#P\subseteq FP^{PPAD}$ imply?

We know $\#P\subseteq {PPAD}\implies PH\subseteq P^{{PPAD}}\subseteq P^{{NP}}$ and the polynomial hierarchy collapses ($FP^{PPAD}=PPAD$ following Emil Jerabek's comment). Can $\#P\subseteq {PPAD}$ ...
• 12.8k
436 views

### Dp completeness of a problem

Given a Boolean formula $\varphi$ over the variables $\{x_1...x_n\}$ , an assignment $T_0$ for $\varphi$ and an integer $k$, I am interested in the following question: Does $k$ is the minimal number ...
• 41
164 views

### On status of Valiant's $NC^2=P^{\#P}$ provability program?

In here it is written 'A most interesting/controversial talk was by Leslie Valiant. He explored paths to try to prove that $NC^2=P^{\#P}\dots$'.... This was a decade back. What is the rationale (at ...
• 12.8k
51 views

### Complexity class of MCS and relation to #p

I was looking for the complexity class of computing MCS: Given a boolean formula $\mathcal{F = c_1 \wedge c_2,...,\wedge c_m}$ represented in CNF, a MCS is a subset of the set of clauses $\mathcal{C}$ ...
149 views

### On $\Delta_i^P$

We know $P\subseteq NP\cap coNP\subseteq\Delta_i^P=P^{\Sigma_{i-1}^P}\subseteq \Sigma_i^P\cap\Pi_i^P=NP^{\Sigma_{i-1}^P}\cap coNP^{\Sigma_{i-1}^P}$. If $P=BPP$ is there a 'higher' randomized class ...
• 12.8k
188 views

### On earlier references for $P=BPP$ and Kolmogorov's possible view on modern breakthroughs involving randomness?

Kolmogorov and Uspenskii in this paper 'http://epubs.siam.org/doi/pdf/10.1137/1132060' speculate P=BPP in 1986. They do this without getting into circuit lower bounds and from a different view which ...
• 12.8k
1 vote
111 views

### Classes with oracles forcing the caller to immediately accept (or reject)?

Usually an oracle operates as a black box, simply returning an yes or no answer to the machine calling it; once it has the result, the caller is free to proceed as it sees fit. However, what happens ...
• 300
533 views

### Where is the counting hierarchy if polynomial hierarchy collapses?

Supposing if $P^{\#P}\subseteq BPP$ then polynomial hierarchy collapses. Does the counting hierarchy collapse as well? Irrespective of $P^{\#P}\subseteq BPP$ are there any collapse results of ...
• 41
106 views

### On analogies between parallel complexity and polynomial time hierarchy structure?

Is it known $\mathsf{RNC=NC\iff P=RP}$ or $\mathsf{BPNC=NC\iff P=BPP}$? Are there any analogies (such as collapse results, problems which suggest analogies such as gcd(in NC) and factoring (in P), ...
• 12.8k
70 views

### What is the smallest complexity class that this problem belongs to?

Given $d>0$ and a complete graph $K_n$ is there an integer $m<d$ such that there is an assignment of vectors from $\Bbb F_2^m$ to every edge such that sum of vectors in every simple cycle is not ...
• 12.8k
892 views

### Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

If it is unknown, are there reasons to believe that they might not be equal?
• 137
302 views

### Non-uniform version for the whole polynomial hierarchy

The non-uniform versions of P, NP and coNP are P/poly, NP/poly and coNP/poly. Similarly, we can define a non-uniform version for each level in the PH. For example: $\Sigma_2$/poly consists of ...
• 183
187 views

### SETH-like hypothesis for machine with oracle access to some level of PH

I am wondering if hypothesis such as Strong Exponential Time Hypothesis (SETH) have been studied for problems being in a higher level of the polynomial hierarchy when we give the machine access to an ...
• 2,164
261 views

### Consequences of a distillation algorithm for PSPACE

The following notion of a distillation algorithm comes from "On Problems Without Polynomial Kernels". Let a language $L$ be given. A distillation algorithm for $L$ takes a given list of input ...
• 5,127
140 views

### $\oplus P$ status in polynomial hierarchy

In Wikipedia it is stated that it is not known if $\mathsf{P^{\oplus P} \mathrel{(=} \oplus P)}$ contains $\mathsf{NP}$, although it is known that $\mathsf{BPP^{\oplus P}}$ contains $\mathsf{PH}$. ...
• 12.8k
281 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 ...
603 views

• 12.8k
194 views

Given a sequence of $n$ propositional formulas $\varphi_1, \cdots, \varphi_n$, a propositional formula $\phi$, a number $1\leq \theta\leq n$. Define $K=\min\{k\mid \wedge_{i=k}^n \varphi_i\not\models ... • 1,345 13 votes 1 answer 285 views ### When does randomization stops helping within PSPACE It is known that adding bounded-error randomization to PSPACE doesn't add power. That is, BPPSAPCE=PSPACE. It is famously unknown whether P=BPP, but it is known that$BPP\subseteq \Sigma_2\cap \Pi_2$.... • 5,531 27 votes 1 answer 928 views ### What are consequences of the collapse of CH? I don't grasp the full complexity of the counting hierarchy$CH$. I understand$CH$is in$PSPACE$, and contains$PH$within its second level, due to the Toda's theorem. But, what would be important ... • 531 18 votes 3 answers 6k views ### Examples of$\Sigma_2^p$complete problems? I need a list of$\Sigma_2^p$complete languages. There are two such problems listed in the Complexity Zoo, namely: Minimum equivalent DNF. Given a DNF formula F and integer k, is there a DNF formula ... • 419 7 votes 1 answer 228 views ### Coding theory and complete problems Coding theory is an useful topic in theoretical computer science. There are known examples of problems coming from coding theory which turn out to be NP complete. My questions are the following:$(1)...
• 12.8k
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 ...