# Tag Info

Accepted

### Structural Complexity Theory References

I don't think there really are canonical references for this stuff (roughly: advanced modern structural complexity theory), but here are some references. This list is partially geared towards my ...
• 37.4k
Accepted

### Is $\sf{P^{NP \cap coNP}} = \sf{NP \cap coNP}$?

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 ...
• 2,768
Accepted

### Complete problem in $\Sigma_2^p$ - $\Sigma_{2}SAT$

No. Since universal quantifiers commute with conjunctions, it is easy to see that $\Sigma_2$-SAT with $\psi$ CNF is in NP. If it's really written like this in the book, it's an error. However, the ...
• 17.8k
Accepted

### It is known that $L \subsetneq PH$?

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 ...
• 27.5k
Accepted

### Is $UP\not=NP$ with respect to random oracle?

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 ...
• 37.4k

### Dp completeness of a problem

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 ...

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

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 ...
Accepted

• 2,004
Accepted

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

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 ...
• 1,598

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

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 ...
• 13.7k

### What are the up-to-date results on explicit lower bounds for $\Sigma_2$ communication complexity?

This paper by Lokam shows a lower bound of $3\log n$ on the $\Sigma_2$-communication complexity of inner product and related functions: https://www.semanticscholar.org/paper/Graph-Complexity-and-Slice-...
• 5,615
Accepted

### Does P^NP=NP imply NP=coNP?

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$ ...
• 11.4k

### Structural Complexity Theory References

Joshua Grochow gave a very detailed list in his answer. I would like to mention a few sources that present more introductory/intermediate material, although these may not be useful for OP (hopefully, ...
• 1,733

### Classes with oracles forcing the caller to immediately accept (or reject)?

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 ...
• 17.8k
Accepted

• 17.8k

### Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?

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 ...
• 37.4k

• 13k
Accepted

### Where does a problem lie which is NP-hard but not QMA-hard?

Yes, an $NP$-hard problem high up in the polynomial hierarchy would likely not be $QMA$-hard, since otherwise $QMA$ would be contained in $PH$, exactly as you point out. In fact, we don't need to look ...
• 2,004
1 vote

### Structural Complexity Theory References

Another quite comprehensive textbook that was not mentioned in the earlier answers is this: Theory of Computational Complexity, by Ding-Zhu Du and Ker-I Ko. Here is the Amazon link to the book: https:/...
• 11.4k
1 vote

### Power of unique counting class

It's unclear if $L$ is a decision problem throughout your question so let's fix some things. Let's denote $L$ to be your decision problem and let $S$ be the functional variant. As Neal mentioned in ...
1 vote
Accepted

### On $\Delta_i^P$

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{...
• 37.4k

Only top scored, non community-wiki answers of a minimum length are eligible