18
The oracle goes back to Stockmeyer in 1983. Heller gave the stronger result that : $BPP = EXP^{NP}$ in a relativized world in 1986. Karpiniski and Verbeek (mentioned in the comments) reprove Heller's result.
16
Marcus Schaefer and Chris Umans have a nice Garey-and-Johnson-esque survey of complete problems in the polynomial hierarchy.
16
To me, one of the most basic and surprising consequences of $\mathsf{NP}=\mathsf{coNP}$ is the existence of short proofs for a whole host of problems where it is very difficult to see why they should have short proofs. (This is sort of taking a step back from "What other complexity implications does this collapse have?" to "What are the very basic, down-to-...
13
Something that has not been mentioned so far (as far as I can see) and that holds in the unrelativized world is the following:
$$PH \subseteq PP \quad\mbox{ if }\quad QMA = PP.$$
This was observed by Vyalyi in this paper and comes from the strengthening of two theorems:
Toda's theorem - Vyalyi shows that one query to a $\sharp P$ oracle is enough for a "$...
11
If we also assume $\mathsf{NP}=\mathsf{RP}$, then the hypothesis would also cause the collapse of randomized classes: $\,\,\mathsf{ZPP}=\mathsf{RP}=\mathsf{CoRP}=\mathsf{BPP}$. Although these are all conjectured to unconditionally collapse into $\mathsf{P}$, anyway, it is still open whether that indeed happens. In any case, $\mathsf{NP}=co\mathsf{NP}$ does ...
11
I don't have a good answer, but in the spirit of complexity, I have some answers which suggest that a good answer may be hard to come by :).
Note that the generalized version of Ladner's Theorem implies that there are infinitely many poly-time degrees strictly in between $\mathsf{\Sigma_i P}$ and any poly-time degree strictly above it. In particular, if the ...
10
First, this result is listed in the complexity zoo: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:N#npiconp. Alternatively, it's possible to prove without much trouble (which I do below).
We want to show that $P^{NP \cap coNP} = NP \cap coNP$. Clearly, one direction is obviously true: $NP \cap coNP \subseteq P^{NP \cap coNP}$. To prove the other ...
9
There is a difficulty with the premise of your question — "when does randomization stops helping within $\mathrm{PSPACE}$ — because it suggests that the computational classes $\mathrm{X}$ such that $\mathrm{P \subseteq X \subseteq PSPACE}$ form some sort of linear hierarchy when this is not evident.
We can illustrate this by comparisons between ...
8
A rather recent result not included in the Schaefer and Umans paper is 2-CLIQUE COLOURING OF PERFECT GRAPHS.
See David Defossez, Complexity of clique-coloring odd-hole-free graphs. J. Graph Theory 62, 2 (October 2009), 139-156, and some recent improvements (2013): Hélio B. Macêdo Filho, Raphael C. S. Machado, Celina M. H. de Figueiredo, Hierarchical ...
8
Yes. Beigel CCC '89 showed $\mathsf{P} \neq \mathsf{UP} \neq \mathsf{NP}$ with probability 1. Combined with Rossman-Servedio-Tan, this gives the result you want. You should always try the Complexity Zoo for questions like this...
7
Your problem is in fact in $\textsf{DP}$-complete. (For $\textsf{DP}$, see: https://complexityzoo.uwaterloo.ca/Complexity_Zoo:D#dp.)
You can show membership in $\textsf{DP}$ by reducing your problem to the $\textsf{DP}$-complete problem SAT-UNSAT, which consists of all pairs $(\varphi_1,\varphi_2)$ of propositional formulas such that $\varphi_1$ is ...
7
Deciding the existence of an "evolutionarily stable strategy" in a normal-form game. See http://www.cs.duke.edu/~conitzer/ess.pdf .
The setup is a 2-player symmetric game. An evolutionarily stable strategy is a (randomized) strategy that is (a) a symmetric nash equilibrium, and (b) there are no good "symmetric deviations": in this equilibrium, if one player ...
6
Let me try to clarify.
Consider the following computational problem: given a mathematical statement (in your favorite axiom system) and a number n given in unary representation, decide whether the statement has a proof of size n.
This is an NP problem: given a proof, one can efficiently verify that it is of size n and that it is a valid proof of the ...
6
The truth of a statement is different from it having a (short) proof in a proof system. The language is expressive but it doesn't mean that all valid statements in the language have short proofs in the system.
The theorem doesn't say that you can check the truth of a statement or even the correctness of an arbitrary long proof or of arbitrary theorems. It ...
6
From Russell Impagliazzo's comment:
As a way of formalizing
what languages are in $\mathsf{P}$ if $\mathsf{P}=\mathsf{NP}$,
Regan introduced the complexity class $\mathsf{H}$.
A language $L$ is in $\mathsf{H}$ if and only if $L$ is in $\mathsf{P}^O$
relative to every oracle $O$ so that $\mathsf{P}^O=\mathsf{NP}^O$.
Thus, $L$ is in $\mathsf{...
6
Well, sure, we know things. I think this is a pretty standard nomenclature for it. This hierarchy collapses if and only if $\mathsf{PH}$ does, exercise:
For one direction, modify the proof of Karp-Lipton to show that if $\mathsf{NP} \subseteq \mathsf{coNP}/poly$ then $\mathsf{PH}$ collapses, and observe that this result relativizes
For the other direction, ...
5
Your argument proves that $\mathsf{NEXPTIME}\subseteq\mathsf{EXPSPACE}$, since if a TM terminates in (nondeterministic) exponential time it cannot write to more than an exponential number of tape cells.
On the contrary, if a TM uses exponential space it can still run in doubly-exponential time, e.g. a TM that increments a binary counter of $2^n$ bits until ...
5
As I wrote in my answer to the other question
let's make the argument constructive and uniform in the number of alternations
by giving an algorithm that solves $\Sigma^P_k$ assuming that
we have a polynomial-time algorithm for SAT and
see what we would get if $k$ is not constant.
Let $M$ be a DTM with two inputs $x$ and $y$.
Think of it as a verifier for ...
5
If you just want oracle separations with $\#P$, you don't need to use the new result of Raz and Tal. You can use the classic Parity/Majority not in $AC^0$ results from the 1980s.
For example, the strongest quantitative version of Parity not in $AC^0$ says that the $n$-bit Parity function cannot be computed by a quasi-polynomial size $AC^0$ circuit of depth ...
4
Below I expand a little bit on the point in Peter's answer by trying to carry out the quantifier removal for more than constant number of steps to see where it fails and if anything can be salvaged from such an attempt.
Let's try to amplify $\mathsf{P}=\mathsf{NP}$ for more than constant number times.
Assume that $\mathsf{P}=\mathsf{NP}$. Therefore there ...
4
Yes, the counting hierarchy collapses in this case: Suppose that $P^{\#P}\subseteq BPP$. We know that $P^{\#P}=P^{PP}$, so $P^{PP}\subseteq BPP$. Consider the second level of the counting hierarchy, $C_2^P=PP^{PP}$. By hypothesis, we have
$$C_2^P=PP^{PP}\subseteq PP^{P^{PP}}\subseteq PP^{BPP}\subseteq PP\subseteq P^{PP}\subseteq BPP $$
So the counting ...
3
First, $\mathrm{PPAD\subseteq FP^{NP}}$, hence $\mathrm{\#P^{PPAD}\subseteq\#P^{NP}\subseteq FP^{\#P}}$. Moreover, $\mathrm{PPAD}$ is closed under Turing reductions, i.e., $\mathrm{FP^{PPAD}\subseteq PPAD}$. Thus, if we assume
$$\mathrm{\#P\subseteq PPAD},$$
then
$$\mathrm{\#P^{PPAD}\subseteq PPAD},$$
which by induction implies
$$\mathrm{FCH=PPAD}.$$
Passing ...
answered Jul 31 '17 at 13:51
Emil Jeřábek supports Monica
10.9k3 gold badges40 silver badges63 bronze badges
3
The question is not entirely clear to me. However, concerning the example that is spelled out more precisely: if a language is recognizable by a poly-time machine with a SAT oracle which must accept whenever the oracle answers “yes”, it is in fact in NP. First, observe that regardless of the oracle answers, we can simulate in polynomial time the only ...
answered May 29 '17 at 16:52
Emil Jeřábek supports Monica
10.9k3 gold badges40 silver badges63 bronze badges
3
An answer to the first question can be found in a paper by Schaefer and Umans, Completeness in the polynomial-time hierarchy: A compendium (2002).
In subsection "Coding and cryptology" (see p. 24), two $\Pi_2^p$-complete problems appear: checking an upper bound on the covering radius of a linear code, and deciding whether a linear code is $r$-identifying ($...
3
Yes, it implies. $P^{NP}$ is the set of languages that are Turing reducible to $NP$ (for example, to $SAT$, or any other $NP$-complete problem). If we take a Boolean formula $F$, then $F\in UNSAT$ holds (meaning that $F$ is not satisfiable), if and only if $\overline{F}$ (the negation of $F$) is satisfiable. Since $UNSAT$ is co-$NP$-complete, and the ...
2
2) The class can be described as the relativization of DP with an NP oracle, hence I would call it $\mathrm{DP^{NP}}$. While other notations exist in the literature as explained in not-A-or-B’s answer, I do not find them very helpful, as I would have no idea what levels exactly of the hierarchies the various indices denote without looking it up.
1) Your ...
answered Aug 10 '17 at 10:41
Emil Jeřábek supports Monica
10.9k3 gold badges40 silver badges63 bronze badges
2
The definition of the class that you are referring to is interesting.
Originally, the definition of the class $D^P$, as the class of the languages that are the intersection of an $NP$ language and a co-$NP$ language, appeared in [1].
Then, the idea behind $D^P$ was generalized to the Boolean Hierarchy ($BH$) [2], which is a hierarchy between $NP$ and $\...
2
Theorem 15.3 of the recent "Parameterized Algorithms" textbook by Cygan et al. states the following:
"Let $L, R ⊆ \Sigma^*$ be two languages. If there exists an OR-distillation of L into R, then $L\in coNP / poly$"
So, I think that if there exists an OR-distillation from a PSPACE-complete language $L$ to itself, then $PSPACE \subseteq coNP/poly$, i.e. not ...
2
Problem 2. answered in references
a. https://arxiv.org/pdf/cs/9907033.pdf
b. http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=19DD617ABDB31709CA0BEF797C283867?doi=10.1.1.60.9357&rep=rep1&type=pdf.
Only top voted, non community-wiki answers of a minimum length are eligible
