On the subexponential-time complexity of CSP

DOI10.1613/JAIR.4540MaRDI QIDQ5176853zbMATH OpenOpenAlexWikidataFDO

Authors Ronald de Haan, Stefan Szeider, Iyad Kanj

Publication date 4 March 2015

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1613/jair.4540

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Time complexity of constraint satisfaction via universal algebra
• Fine-grained time complexity of constraint satisfaction problems
• The Time Complexity of Constraint Satisfaction
• The (Coarse) Fine-Grained Structure of NP-Hard SAT and CSP Problems
• Maximum satisfiability and subexponential time

Cited in

(10)

• Improved FPT algorithms for weighted independent set in bull-free graphs
• Acyclic orders, partition schemes and CSPs: unified hardness proofs and improved algorithms
• Tractability in constraint satisfaction problems: a survey
• Precise upper and lower bounds for the monotone constraint satisfaction problem
• Maximum satisfiability and subexponential time
• The Time Complexity of Constraint Satisfaction
• Why are CSPs based on partition schemes computationally hard?
• Fine-grained time complexity of constraint satisfaction problems
• Time complexity of constraint satisfaction via universal algebra
• A survey on the fine-grained complexity of constraint satisfaction problems based on partial polymorphisms

This page was built for publication: On the subexponential-time complexity of CSP

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5176853)