  Large complexity classes, like the exponential time hierarchy, received
little attention in terms of finding complete problems. In this work a
generalization of propositional logic is investigated which fills this gap with
the introduction of Boolean higher-order quantifiers or equivalently Boolean
Skolem functions. This builds on the important results of Wrathall and
Stockmeyer regarding complete problems, namely QBF and QBF-k, for the
polynomial hierarchy. Furthermore it generalizes the Dependency QBF problem
introduced by Peterson, Reif and Azhar which is complete for NEXP, the first
level of the exponential hierarchy. Also it turns out that the hardness results
do not collapse at the consideration of conjunctive and disjunctive normal
forms, in contrast to plain QBF.
