The polynomial-hierarchy tag has no wiki summary.
7
votes
0answers
290 views
Interesting SUBSET-SUM problems
I know the following variants of SUBSETSUM problems: $ \mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L} $ (Elberfeld at. al., 2010), NP-complete $ \mathtt{SUBSETSUM} $, and NEXP-complete $ ...
0
votes
1answer
170 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 ...
7
votes
2answers
340 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 ...
11
votes
1answer
312 views
Oracle relative to which $\mathsf{BPP}$ is not contained in $Δ_2 \mathsf{P}$
Complexity Zoology by Greg Kuperberg states that there is a language $X$ such that $\mathsf{BPP}^X \nsubseteq \mathsf{\Delta_2 \mathsf{P}}^X$ — in other words, $\mathsf{BPP}^X \nsubseteq ...
6
votes
1answer
456 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 ...
3
votes
2answers
901 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 ...
2
votes
2answers
337 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. ...
29
votes
0answers
810 views
Can one amplify P=NP beyond P=PH?
In Descriptive Complexity, Immerman has
Corollary 7.23. The following conditions are equivalent:
1. P = NP.
2. Over finite, ordered structures, FO(LFP) = SO.
This can be thought of as ...
10
votes
5answers
665 views
Why doesn't P=NP imply P=AP (i.e. P=PSPACE)?
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 ...
14
votes
2answers
493 views
Is there a Time Hierarchy theorem for PH?
Is it true that there are problems in the polynomial hierarchy solvable in time $O(n^k)$ (by an alternating Turing machine in some level of the polynomial hierarchy) that are not solvable in ...
1
vote
1answer
202 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 ...
7
votes
1answer
282 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 ...
29
votes
4answers
2k views
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 ...
26
votes
3answers
1k views
A decision problem which is not known to be in PH but will be in P if P=NP
Edit: As Ravi Boppana correctly pointed out in his answer and Scott Aaronson also added another example in his answer, the answer to this question turned out to be “yes” in a way which I had not ...