The complexity class Θ^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 Θ^P_k to the k-th level of the polynomial hierarchy. We show that problems in Θ^P_k are also those whose solution involves deciding, for two given sets A and B of instances of two Σ^P_{k−1}-complete (or Π^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 Θ^P_k-hardness. We also define the general problem Comp-Valid_k, which is proven here Θ^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 Θ^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 Θ^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 Θ^P_2-hardness of the Max voting scheme over mCP-nets is easily obtained via the new characterization of Θ^P_k introduced in this paper.
A novel characterization of the complexity class Θ^P_k based on counting and comparison / LUKASIEWICZ THOMAS; MALIZIA E. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - STAMPA. - 694:(2017), pp. 21-33. [10.1016/j.tcs.2017.06.023]
A novel characterization of the complexity class Θ^P_k based on counting and comparison
MALIZIA E
2017
Abstract
The complexity class Θ^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 Θ^P_k to the k-th level of the polynomial hierarchy. We show that problems in Θ^P_k are also those whose solution involves deciding, for two given sets A and B of instances of two Σ^P_{k−1}-complete (or Π^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 Θ^P_k-hardness. We also define the general problem Comp-Valid_k, which is proven here Θ^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 Θ^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 Θ^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 Θ^P_2-hardness of the Max voting scheme over mCP-nets is easily obtained via the new characterization of Θ^P_k introduced in this paper.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
