The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
From MaRDI portal
Publication:2235760
DOI10.1016/j.tcs.2021.09.006OpenAlexW3196775331WikidataQ115566727 ScholiaQ115566727MaRDI QIDQ2235760
Publication date: 21 October 2021
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2021.09.006
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Strong partial clones and the time complexity of SAT problems
- The complexity of surjective homomorphism problems-a survey
- Graph properties checkable in linear time in the number of vertices
- On the algebraic structure of combinatorial problems
- Which problems have strongly exponential complexity?
- Constructing NP-intermediate problems by blowing holes with parameters of various properties
- What makes propositional abduction tractable
- Weak bases of Boolean co-clones
- The complexity of soft constraint satisfaction
- The Approximability of Constraint Satisfaction Problems
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- On the Limits of Sparsification
- The power of primitive positive definitions with polynomially many variables
- Complexity Classifications for Propositional Abduction in Post's Framework
- Fast FAST
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Twice-Ramanujan Sparsifiers
- Fine-Grained Time Complexity of Constraint Satisfaction Problems
- A Proof of the CSP Dichotomy Conjecture
- Function Algebras on Finite Sets
- The complexity of satisfiability problems
- A Complete Classification of the Complexity of Propositional Abduction
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Partial Polymorphisms and Constraint Satisfaction Problems
- The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)
- On the complexity of \(k\)-SAT
This page was built for publication: The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems