×

\( \Theta_2^p\)-completeness: A classical approach for new results. (English) Zbl 1044.68062

Kapoor, Sanjiv (ed.) et al., FST TCS 2000: Foundations of software technology and theoretical computer science. 20th conference, New Delhi, India, December 13–15, 2000. Proceedings. Berlin: Springer (ISBN 3-540-41413-4). Lect. Notes Comput. Sci. 1974, 348-360 (2000).
Summary: In this paper we present an approach for proving \( \Theta_2^p\)-completeness. There are several papers in which different problems of logic, of combinatorics, and of approximation are stated to be complete for parallel access to NP, i.e. \( \Theta_2^p\)-complete. There is a special acceptance concept for nondeterministic Turing machines which allows a characterization of \( \Theta_2^p\) as a polynomial-time bounded class. This characterization is the starting point of this paper. It makes a master reduction from that type of Turing machines to suitable boolean formula problems possible. From the reductions we deduce a couple of conditions that are sufficient for proving \( \Theta_2^p\)-hardness. These new conditions are applicable in a canonical way. Thus we are able to do the following: (i) we can prove the \( \Theta_2^p\)-completeness for different combinatorial problems (e.g. max-card-clique compare) as well as for optimization problems (e.g. the Kemeny voting scheme), (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).
For the entire collection see [Zbl 0952.00044].

MSC:

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: Link