The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems

DOI10.1016/j.tcs.2021.09.006OpenAlexW3196775331WikidataQ115566727 ScholiaQ115566727MaRDI QIDQ2235760

Yanyan Li

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

zbMATH Keywords

constraint satisfaction problemsuniversal algebrafine-grained complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (1)

General lower bounds and improved algorithms for infinite-domain CSPs

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