scientific article; zbMATH DE number 2080215
From MaRDI portal
Publication:4472458
Recommendations
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
- Three \(\sum^ P_ 2\)-complete problems in computational learning theory
- A note on complete problems for complexity classes
- Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP
- Characterizations of some complexity classes between \(\Theta_2^{\mathrm{P}}\) and \(\Delta_2^{\mathrm{P}}\)
Cited in
(16)- Anyone but him: the complexity of precluding an alternative
- Complexity of stability
- Polynomial algorithms for protein similarity search for restricted mRNA structures
- A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison
- The complexity of comparing optimal solutions
- Recognizing when heuristics can approximate minimum vertex covers is complete for parallel access to NP
- Hybrid Elections Broaden Complexity-Theoretic Resistance to Control
- The price of connectivity for dominating set: upper bounds and complexity
- Open problems in a logic of gossips
- Complexity of Stability.
- Completing the c₂ completion conjecture for p=2
- Beyond recognizing well-covered graphs
- On the complexity of entailment in existential conjunctive first-order logic with atomic negation
- The complexity of Kemeny elections
- Guarantees for the success frequency of an algorithm for finding Dodgson-election winners
- Dichotomy for voting systems
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4472458)
