Let us say that there exists a $\mathsf{NP}$-reduction from a problem $A$ to another problem $B$ when there exists a non-deterministic, polynomial-time Turing machine $T$ such that for each $a \in A$, one of the possible outputs of $T(a)$ is in $B$ (and conversely, if one output $T(a) \in B$, then $a \in A$). $\mathsf{NP}$ reductions are discussed with relevant citations in the opening pages of this article.

A complexity class $\mathcal{C}$ is closed under $\mathsf{NP}$-reductions, if whenever a problem $A$ can be $\mathsf{NP}$-reduced to some $B \in \mathcal{C}$, we have $A \in \mathcal{C}$. (I think) equivalently, the class $\mathcal{C}$ is closed under $\mathsf{NP}$-reductions if whenever $B$ is $\mathcal{C}$-complete and there exists a $\mathsf{NP}$ reduction from $A$ to $B$, there also exists a polynomial-time (deterministic) many-one reduction from $A$ to $B$.

Of course, any class $\mathcal{C}$ that is closed under $\mathsf{NP}$-reductions must include $\mathsf{NP}$, but it isn't obvious to me that any class containing $\mathsf{NP}$ is closed under $\mathsf{NP}$-reductions. Indeed, on p. 545 of this article it is claimed that closure under $\mathsf{NP}$-reductions is nontrivial and that every class in the series $\mathsf{NP} \subseteq \exists\mathbf{R} \subseteq \mathsf{PSPACE}$ is closed under $\mathsf{NP}$-reductions.

Here is my question: What is a non-trivial condition on a complexity class $\mathcal{C}$, such that when $\mathcal{C}$ satisfies that condition, it is closed under $\mathsf{NP}$ reductions?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.