Consider the following problem:Input: (G1, G2) where G1 and G2 are undirected graphsQuestion:  Is the size of the max independent set of G1 at least as large as the size of the max independent set of G2?This seems like a fairly natural question to ask, and yet I have been unable to find a complexity class for which this problem is complete.  Does anyone know of such?  As a starting point, it is readily seen that the problem is NP-hard and contained in P with access to an NP oracle with log many queries.
Complexity of Comparative Independent Set Decision Problem
cc.complexity theory
This problem is indeed complete for the class of polynomial time Turing machines with access to an NP oracle with log many queries (also known as $\Theta_2^p$).  The result appears in a 2000 FST TCS paper by Spakowski and Vogel titled $\Theta_2^p$-Completeness: A Classical Approach for New Results.  The proof presented there and a proof that I arrived at independently both rely on the $\Theta_2^p$-completeness criterion of Wagner (Bounded Query Classes SIAM Journal on Computing archive Volume 19 Issue 5, Oct. 1990).