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.