There is a special acceptance concept for nondeterministic Turing machines which allows a characterization of Θp _in2 ^sup 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 Θp _in2 ^sup -hardness. These new conditions are applicable in a canonical way. Thus we are able to do the following: (i) we can prove the Θp _in2 ^sup 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 Θp _in2 ^sup (e.g. for the Dodgson voting scheme), and (iii) we can transfer this technique for proving Δp _in2 ^sup -completeness (e.g. TSPcompare).