13 votes
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 ...
Joshua Grochow's user avatar
11 votes
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 ...
Mikhail Rudoy's user avatar
11 votes
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 ...
Emil Jeřábek's user avatar
8 votes
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 ...
Ryan Williams's user avatar
8 votes
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 ...
Joshua Grochow's user avatar
7 votes

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 ...
Ronald de Haan's user avatar
7 votes

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 ...
not A or B's user avatar
7 votes
Accepted

Can one amplify P=NP beyond P=PH?

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 $...
6 votes
Accepted

Non-uniform version for the whole polynomial hierarchy

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-...
Joshua Grochow's user avatar
5 votes

What are consequences of the collapse of CH?

You could also ask similar questions about the polynomial hierarchy. The consensus in the research community is that PH is unlikely to collapse ... but I can't think of any dramatic consequences that ...
Eric Allender's user avatar
5 votes

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

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,...
Emil Jeřábek's user avatar
5 votes

Can one amplify P=NP beyond P=PH?

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 ...
Kaveh's user avatar
  • 21.6k
5 votes

Where is the counting hierarchy if polynomial hierarchy collapses?

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, $...
Lieuwe Vinkhuijzen's user avatar
5 votes
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 ...
Nicola Gigante's user avatar
5 votes

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 ...
Robin Kothari's user avatar
3 votes
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$ ...
Andras Farago's user avatar
3 votes

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-...
Or Meir's user avatar
  • 5,370
3 votes

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, ...
Cyriac Antony's user avatar
3 votes

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 ...
Emil Jeřábek's user avatar
3 votes
Accepted

Consequences of a distillation algorithm for PSPACE

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\...
Michael Lampis's user avatar
3 votes
Accepted

What does $\#P\subseteq FP^{PPAD}$ imply?

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 ...
Emil Jeřábek's user avatar
2 votes

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 ...
Joshua Grochow's user avatar
2 votes

Possibility of hierarchy with $UP$ class?

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&...
Turbo's user avatar
  • 12.8k
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:/...
Andras Farago's user avatar
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 ...
veryinteresting's user avatar
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{...
Joshua Grochow's user avatar

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