# Questions tagged [polynomial-hierarchy]

The tag has no usage guidance.

55 questions
Filter by
Sorted by
Tagged with
33 views

### Are those two Sum-Of-Squares approach for unconstrained polynomial optimization related? [closed]

This is a crosspost of mathoverflow/345282 I found 2 approaches to solve an unconstrained polynomial optimization problem using the Lasserre / SOS hierarchy: $$\inf_{x\in\mathbb{R}^n}\quad p(x)$$ ...
300 views

92 views

### Where in $PH$ are these problems?

Is 'Given two codes with alphabet in $\mathbb F_2$ with Generator matrices $G_1$ and $G_2$ do they have the same minimum distance?' in $NP$ or is it in $coNP$ (I can see it in $P^{NP}$)? If $G_1$ is ...
132 views

### Lower bound on alternations needed in $BQP$ versus $PH$ result?

What is the fastest $f(n)$ the relatively new result of oracle separation of $\mathsf{BQP}$ from $\mathsf{PH}$ provides such that ${\#\mathsf{SAT}}\not\subseteq\mathsf{FP}^{\mathsf{PH}[O(f(n))]}$ ...
123 views

### Canonical complete problem for $\mathrm{FP}^{\Sigma^p_2}$

Given a $\Sigma^p_2$-complete oracle (i.e., $\Sigma_2 \mathrm{SAT}$), I have a problem that requires to call this oracle polynomially many times and returns an integer. Essentially, this is a function ...
158 views

### Does P^NP=NP imply NP=coNP? [closed]

If you have it, the proof would be appreciated. Note: P^NP means P with NP oracle
114 views

### Proof of Sipser-Lautmann Theorem

I have written the following answer as an attempt to prove a variation of Sispser-Lautmann theorem, but it was rejected without any comments. I would appreciate if anyone can find the flaws in this ...
568 views

### What are the problems in EXPSPACE \ EXPTIME?

Based on the diagram below (from Papadimitriou's book) we can see that PSPACE ⊆ EXPTIME ⊆ EXPSPACE. We know that PSPACE ⊊ EXPSPACE, which means that there are problems that can be solved in polynomial ...
120 views

252 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$....
717 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 ...
4k 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 ...
199 views

72 views

### Weight enumerator and levels of polynomial hierarchy

Let $A_i$ be the number of codewords in a binary linear code $\mathcal{C}$ of weight $i$. It is known that: $A_k$ is in $P$, where $k = \mathcal{O}(\log_2 n)$. $A_{n}$ is in $\#P-Complete$, ...
127 views

### Computing the permanent with polylog size matrices

The complexity of computing the permanent of a $l\times l$ binary matrix is known to be $\#\mathsf{P}$-complete, from the famous result of Valiant, where $l = \Theta(n)$. We know that the problem is ...
405 views

### Is the collapse of $PH$ known to extend downward to classes in-between its levels?

Contained in-between each level of the polynomial hierarchy are various complexity classes, including $\Delta_i^{\text{P}}$, $\text{DP}$, $\text{BH}_k$, and $\Sigma_i^\text{P} \cap \Pi_i^\text{P}$. ...
1k views

### An analog of DP for the second level of the polynomial hierarchy

The complexity class DP can be defined as the set of all languages that are the intersection of an NP language with a coNP language. I have a language for which I wish to determine the exact ...
1k views

### On the proof of Meyer's Theorem

Meyer's theorem is one of the classical results about collapse of the polynomial hierarchy such as famous Karp Lipton's theorem, and states that $EXP \subseteq P/poly \Rightarrow EXP = \Sigma_{2}^{p}$...
819 views

610 views

### Complexity of Exactly $A$-SAT

Let define the "Exactly $A$-SAT" problem : Given a CNF formula $F$ and a set $A$ of positive integers, is it true that the number of models of $F$ is in $A$? What is the complexity of Exactly $A$-...
3k views

### Consequences of $NP=coNP$ and $P\ne NP$?

We know that if $P=NP$ then the whole PH collapses. What if the polynomial hierarchy collapses partially ? (Or how to understand that PH could collapse above a certain point and not below ?) In ...
613 views

### Is there a PSPACE-intermediate language?

Suppose PH is strictly contained in PSPACE. Is there a problem in PSPACE that is not in PH and not PSPACE-complete? I encountered a language that is in PSPACE. The question is whether it's in PH. So ...
It is well known that if $\mathbf{P}=\mathbf{NP}$ then the polynomial hierarchy collapses and $\mathbf{P}=\mathbf{PH}$. This can easily be understood inductively using oracle machines. The question ...