A novel characterization of the complexity class Theta(P)(k) based on counting and comparison

作者：Lukasiewicz Thomas; Malizia Enrico^*

来源：Theoretical Computer Science, 2017, 694: 21-33.

DOI：10.1016/j.tcs.2017.06.023

• Polynomial hierarchy
• Computation with oracles
• Counting and comparison
• Theta(P)(k)
• Theta(P)(k)-complete problem

The complexity class Theta(P)(2), 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 Theta(P)(2) to the k-th level of the polynomial hierarchy. We show that problems in Theta(P)(2) are also those whose solution involves deciding, for two given sets A and B of instances of two Sigma(P)(k-1)-complete (or Pi(P)(k-1)-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 Theta(P)(2)-hardness. We also define the general problem COMP-VALID(k), which is proven here Theta(P)(k+1)-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 Theta(P)(2)-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 Theta(P)(k)-hardness of problems involving the counting and comparison of the number of "yes"-instances in two sets. We support this by showing that the Theta(P)(2)-hardness of the Max voting scheme over mCP-nets is easily obtained via the new characterization of Theta(P)(k) introduced in this paper.

• 出版日期2017-9-19