A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison

DOI10.1016/j.tcs.2017.06.023zbMath1373.68231OpenAlexW2729308697WikidataQ57942024 ScholiaQ57942024MaRDI QIDQ2404077

Enrico Malizia, Thomas Lukasiewicz

Publication date: 12 September 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.06.023

zbMATH Keywords

polynomial hierarchycomputation with oracles\(\Theta_k^{\mathrm{P}}\)-complete problemcomplexity class \(\Theta_k^{\mathrm{P}}\)counting and comparison

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (6)

Inconsistency-tolerant query answering for existential rules ⋮ Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting ⋮ Stability, vertex stability, and unfrozenness for special graph classes ⋮ Unnamed Item ⋮ On the complexity of the clone membership problem ⋮ Complexity results for preference aggregation over (\(m\))CP-nets: Pareto and majority voting

Uses Software

• CP-nets

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of core, kernel, and bargaining set
• The complexity of Kemeny elections
• \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP]
• The complexity of optimization problems
• More complicated questions about maxima and minima, and some closures of NP
• On truth-table reducibility to SAT
• The polynomial-time hierarchy
• Complete sets and the polynomial-time hierarchy
• Exact complexity of the winner problem for Young elections
• Default reasoning from conditional knowledge bases: Complexity and tractable cases
• The Complexity of the Nucleolus in Compact Games
• Bounded Query Classes
• Non-Transferable Utility Coalitional Games via Mixed-Integer Linear Constraints
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Exact analysis of Dodgson elections
• Relativized logspace and generalized quantifiers over finite ordered structures
• NP trees and Carnap's modal logic
• Achieving new upper bounds for the hypergraph duality problem through logic
• Reducibility among Combinatorial Problems
• The complexity class θp2: Recent results and applications in AI and modal logic
• The complexity of theorem-proving procedures

This page was built for publication: A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison