On the Capture of Complexity Classes using Logic (1991)

Author(s): Stewart, I.A.

Abstact: We partially solve a conjecture of Gurevich and show that is NP∩co-NP is captured by a logic that is closed under disjunction or existential quantification the NP = co-NP. We also obtain similar results for other complexity classes.