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

Abstract

The complexity class Θ₂^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₁, demonstrates itself as a very intuitive Θ₂^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 Θ₂^P-hardness of the Max voting scheme over mCP-nets is easily obtained via the new characterization of Θ_k^P introduced in this paper.