The Time Complexity of Constraint Satisfaction

DOI10.1007/978-3-540-79723-4_18zbMath1142.68376OpenAlexW1515598460MaRDI QIDQ3503589

Patrick Traxler

Publication date: 5 June 2008

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79723-4_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (14)

Assigning channels via the meet-in-the-middle approach ⋮ The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems ⋮ Lower Bounds for the Graph Homomorphism Problem ⋮ Channel assignment via fast zeta transform ⋮ Unnamed Item ⋮ New plain-exponential time classes for graph homomorphism ⋮ General lower bounds and improved algorithms for infinite-domain CSPs ⋮ Unnamed Item ⋮ Refining complexity analyses in planning by exploiting the exponential time hypothesis ⋮ An initial study of time complexity in infinite-domain constraint satisfaction ⋮ New Plain-Exponential Time Classes for Graph Homomorphism ⋮ Testing the Complexity of a Valued CSP Language ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ On Super Strong ETH

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• NP is as easy as detecting unique solutions
• Matching is as easy as matrix inversion
• Which problems have strongly exponential complexity?
• A condition for matchability in hypergraphs
• The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Worst-case time bounds for coloring and satisfiability problems
• An LP-Designed Algorithm for Constraint Satisfaction
• On the complexity of \(k\)-SAT

This page was built for publication: The Time Complexity of Constraint Satisfaction