Questions tagged [polynomial-hierarchy]
The polynomial-hierarchy tag has no usage guidance.
67
questions
6
votes
3
answers
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
5
votes
0
answers
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
0
answers
82
views
$NP\subseteq P/poly\implies PH\subseteq P/poly$ [closed]
We know if $NP\subseteq P/poly$ then $PH=\Sigma_2$ Then We want to show that $\Sigma_2-SAT\in P/poly$. Now $$\phi\in \Sigma_2-SAT\iff \exists\ x\in\{0,1\}^{p_1(n)}\ \forall\ y\in \{0,1\}^{p_2(n)},\ \...
- 288
3
votes
1
answer
95
views
What are the up-to-date results on explicit lower bounds for $\Sigma_2$ communication complexity?
What are the best polylogarithmic lower bounds known for $\Sigma_2$-communication complexity on an explicit function? Are there any known candidate functions for $O(n^\epsilon)$ communication ...
- 241
3
votes
0
answers
68
views
Exponential version of $CC^0$
(In this question, "uniform" will mean $DLOGTIME$-uniform.)
In Allender's 1998 paper "The Permanent Requires Large Uniform Threshold Circuits", he talks about the "exponential ...
- 1,204
0
votes
1
answer
65
views
Power of unique counting class
One question that recently encountered is the following, suppose I have a task $L$ which has input length $n$, the problem is in the $\text{NP}$ and I promise that there is a unique solution. (The ...
4
votes
0
answers
160
views
Computational Complexity of MIN-EQ-3-CNF
Consider the decision problem:
MIN-EQ-CNF= $\{\langle\phi, k\rangle |\exists \text{CNF formula } \psi \text{ of size }\leq k\text{ that is equivalent to the CNF formula }\phi\}$
CNF is a Boolean ...
- 468
8
votes
1
answer
670
views
Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$
It is known that the following problem is complete in $\Sigma_2^p$:
$\Sigma_{2}SAT$ : Given a quantified boolean formula $\theta = \exists x_1,...,x_l\forall y_1,...,y_m\psi$, where $\psi$ is a ...
10
votes
1
answer
182
views
It is known that $L \subsetneq PH$?
Is it known whether $Logspace$ is strictly contained in the polynomial time hierarchy ?
Are there oracles relative to which these classes are equal / distinct ?
- 296
2
votes
0
answers
72
views
Logarithmic queries to $\Sigma_i^P$ oracle and the Boolean hiearchies
If I understood correctly (the complexity zoo, wikipedia, and some of the cited articles), the class $\textsf{P}^{\textsf{NP}[\log]}$, also known as $\Theta_2^{\textsf{P}}$, sits at the top of the ...
- 803
2
votes
0
answers
40
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)$$
...
- 121
9
votes
1
answer
338
views
Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?
We think that $\mathsf{PH}$ does not collapse, and that $\mathsf{PP}$ is not in $\mathsf{P}$.
Suppose on the contrary that $\mathsf{PH}$ does collapse, say even $\mathsf{P}= \mathsf{NP}$.
$\mathsf{...
- 12.8k
2
votes
1
answer
190
views
Possibility of hierarchy with $UP$ class?
I am not sure if this is a cheap query. However I am unable to find this myself. So I am posting here. The standard complexity class is built with $NP$ and $coNP$ and leads up to $PSPACE$. The ...
- 12.8k
3
votes
0
answers
127
views
Examples of ineffective PH collapse theorems?
What are some examples of theorems of the form "If $X$, then $PH$ collapses", but where the proof does not say which level $PH$ collapses to?
The canonical example would be "If $PH = PSPACE$, then $...
- 3,243
4
votes
0
answers
103
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 ...
- 12.8k
2
votes
1
answer
152
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))]}$ ...
- 12.8k
1
vote
0
answers
189
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 ...
- 11
-3
votes
1
answer
321
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
1
vote
0
answers
140
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 ...
- 21
0
votes
1
answer
1k
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 ...
- 127
5
votes
1
answer
194
views
Is $UP\not=NP$ with respect to random oracle?
It is shown in An average-case depth hierarchy theorem for Boolean circuits a random oracle makes $PH$ infinite.
Is it possible to also show $UP\not=NP\not=\Sigma_2^P\not=\Sigma_3^P\not=\Sigma_4^P\...
- 12.8k
3
votes
0
answers
118
views
On approximating problems in $\#P$
We know that for every counting problem $\#A$ in $\#P$, there is a probabilistic algorithm
$\mathcal C$ that on input $x$, computes with high probability a value $v$ such that $$(1 − ε)\#A(x) ≤ v ≤ (1 ...
- 12.8k
2
votes
1
answer
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
3
votes
1
answer
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
4
votes
0
answers
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
2
votes
0
answers
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}$ ...
- 21
3
votes
1
answer
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
4
votes
0
answers
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
1
answer
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
4
votes
1
answer
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
2
votes
0
answers
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
2
votes
0
answers
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
8
votes
1
answer
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
8
votes
1
answer
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
7
votes
0
answers
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
9
votes
1
answer
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
0
votes
0
answers
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
3
votes
0
answers
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 ...
- 342
2
votes
1
answer
603
views
Is there a problem currently known to be outside class $\mathsf{NP}\cup\mathsf{coNP}$ but inside $\mathsf{BPP}$?
May be this is trivial but I do not know the answer.
As far as we know $$\mathsf{BPP}\subseteq\mathsf{\Sigma}_2\cap\mathsf{\Pi}_2$$ holds.
As far as we know $$\mathsf{NP}\cup\mathsf{coNP}\subseteq\...
- 12.8k
4
votes
0
answers
98
views
Are there any non-relativized separations between $L$ and $PH$?
In one sense, $P$ vs. $PSPACE$ is the "easiest" first step to showing $P \neq NP$... and this is one you hear often about. In a different sense, you could take $L$ at one end and then $PH$ at the ...
- 807
1
vote
0
answers
71
views
Analogues of different complexity classes in various models
We suspect following relation:
$$TC^0\subsetneq NC^1\subsetneq L\subsetneq NL\subsetneq AC^1\subsetneq NC^2\subsetneq P\subsetneq NP\subsetneq PH\subsetneq PSPACE$$ in Turing/boolean circuit ...
- 12.8k
4
votes
0
answers
194
views
A SAT related question
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
5
votes
0
answers
131
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 ...
- 323
4
votes
0
answers
121
views
Gradual increase in hardness from P to PH of #SAT
We know that counting the number of solutions to $3-SAT$ is the canonical $\#P-Complete$ problem. Equivalently, it is the canonical $PH-Hard$ problem.
However, counting the number of solutions to $3-...
- 323
2
votes
0
answers
74
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$, ...
- 323
3
votes
0
answers
135
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 ...
- 323