$\Theta_2^p$-completeness: A classical approach for new results

Joerg Vogel, Holger Spakowski

To appear at Foundations of Software Technology and Theoretical Computer Science (FSTTCS2000), New Delhi, India, December 13-15 2000


In this paper we present an approach for proving $\Theta_2^p$-completeness. Recently there are several papers in which the complexity of different problems of logic, of combinatorics, of approximation, resp. are stated to be complete for parallel access to NP, i.e. $\Theta_2^p$-complete. As an example there is a paper by Hemaspaandra/Hemaspaandra/Rothe, where they proved that Dodgson Elections - a voting system defined by Lewis Carroll more than 100 years before and therefore without any concepts of computability and complexity - is $\Theta_2^p$-complete answering an open question of Bartholdi/Tovey/Trick. In Spakowski/Vogel is introduced a special concept for nondeterministic Turing machines which allows a characterization of $\Theta_2^p$ as a polynomial time bounded class. That characterization is the starting point of this paper. It enables us to construct into two versions a ``master reduction'' from that type of Turing machines to a suitable boolean formula problem. From the reductions we deduce two conditions which are sufficient for proving $\Theta_2^p$-hardness. The well-known and useful condition stated by Wagner for proving $\Theta_2^p$-hardness appears as a consequence of the new conditions. These new conditions are applicable in a more canonical way. Thus we are able to do the following: (i) we can prove the $\Theta_2^p$-completeness for different combinatorical problems (e.g. max-card-clique compare) as well as for optimization problems (e.g. the Kemeny voting scheme, which was an open problem stated in Bartholdi et al.), (ii) we can simplify known proofs for $\Theta_2^p$-completeness (e.g. for the Dodgson voting scheme), and (iii) we can transfer this technique for proving $\Delta_2^p$-completeness (e.g. TSPcompare).

Server START Conference Manager
Update Time 14 Aug 2000 at 17:41:23
Maintainer fsttcs20@cse.iitd.ernet.in.
Start Conference Manager
Conference Systems