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).
