18
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-...
16
Marcus Schaefer and Chris Umans have a nice Garey-and-Johnson-esque survey of complete problems in the polynomial hierarchy.
12
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 ...
12
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
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
This is equivalent to $LOGSPACE≠NP$ (which is obviously open). The proof of that equivalence relativizes (at least under the usual oracle models).
And there are oracles making $LOGSPACE = NP$ (the PSPACE-complete TQBF works) and making them not equal (the oracle separating P from NP works).
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
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, ...
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{...
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
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 ...
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 ...
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 ...
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 ...
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 ...
3
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 ...
3
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 $\...
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 ($...
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 ...
2
The scaled down version of $\mathsf{PH}$ versus $\mathsf{PP}$ is $\mathsf{AC}^0$ versus $MAJ \circ \mathsf{AC}^0$, and we know that for the latter there is an exponential separation. Of course, this separation doesn't propagate exponentially up, but you could take this as philosophical evidence that $\mathsf{PH}$ is different enough from $\mathsf{PP}$ that ...
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.
1
Yes, one can define $BP\Delta_i^P$. Indeed, for any class $\mathcal{C}$ one can define $\mathsf{BP} \cdot \mathcal{C}$ as $L \in \mathsf{BP} \cdot \mathcal{C}$ iff there is a language $L' \in \mathcal{C}$ such that
$$ x \in L \Rightarrow (x,y) \in L' \text{ for at least 2/3 of the $y$ of length } \leq poly(x) $$
$$ x \notin L \Rightarrow (x,y) \in L' \...
1
I am not sure I understand your question. Let $L_M(k)=\{(x,i,t)$ for which on input $x$ we have that the $k$-th bit of $z_{i,t}$ is $1$. This language is in EXP, thus also in P/poly. Putting together these circuits for different values of $k$, we get the multi-output circuit.
1
The main credit should go to John Fearnley!
Here is a PSPACE-complete problem given in (John Fearnley, Marcin Jurdzinski: Reachability in Two-Clock Timed Automata Is PSPACE-Complete. ICALP (2) 2013: 212-223):
\begin{equation}
\mathtt{SUBSETSUM\mbox{-}GAME}=\{ S~ \forall(a_1 , b_1) \exists(e_1,f_1) \cdots \forall(a_n , b_n) \exists(e_n,f_n) \},
\end{...
Only top voted, non community-wiki answers of a minimum length are eligible
