# A Novel Characterization of the Complexity Class Θ^P_k Based on Counting and Comparison

*Thomas Lukasiewicz and Enrico Malizia*

### Abstract

The complexity class Θ_{2}^{P}, which is the class of languages recognizable by deterministic Turing machines in polynomial time with at most logarithmic many calls to an NP oracle, received extensive attention in the literature. Its complete problems can be characterized by different specific tasks, such as deciding whether the optimum solution of an NP problem is unique, or whether it is in some sense “odd” (e.g., whether its size is an odd number). In this paper, we introduce a new characterization of this class and its generalization Θ_{k}^{P} to the *k*-th level of the polynomial hierarchy. We show that problems in Θ_{k}^{P} are also those whose solution involves deciding, for two given sets *A* and *B* of instances of two Σ_{k-1}^{P}-complete (or Π_{k-1}^{P}-complete) problems, whether the number of “yes”-instances in *A* is greater than those in *B*. Moreover, based on this new characterization, we provide a novel sufficient condition for Θ_{k}^{P}-hardness. We also define the general problem Comp-Valid* _{k}*, which is proven here Θ

_{k+1}

^{P}-complete. Comp-Valid

_{k}is the problem of deciding, given two sets

*A*and

*B*of quantified Boolean formulas with at most

*k*alternating quantifiers, whether the number of valid formulas in

*A*is greater than those in

*B*. Notably, the problem Comp-Sat of deciding whether a set contains more satisfiable Boolean formulas than another set, which is a particular case of Comp-Valid

_{1}, demonstrates itself as a very intuitive Θ

_{2}

^{P}-complete problem. Nonetheless, to our knowledge, it eluded its formal definition to date. In fact, given its strict adherence to the count-and-compare semantics here introduced, Comp-Valid

_{k}is among the most suitable tools to prove Θ

_{k}

^{P}-hardness of problems involving the counting and comparison of the number of “yes”-instances in two sets. We support this by showing that the Θ

_{2}

^{P}-hardness of the Max voting scheme over

*m*CP-nets is easily obtained via the new characterization of Θ

_{k}

^{P }introduced in this paper.