Constraint satisfaction problems in non-deterministic logarithmic space

DOI10.1007/3-540-45465-9_36MaRDI QIDQ4737176zbMATH OpenFDO

Authors Víctor Dalmau

Publication date 11 August 2004

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2380/23800414.htm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Linear Datalog and Bounded Path Duality of Relational Structures
• On constraint satisfaction problems below P
• On constraint satisfaction problems below P
• CSP duality and trees of bounded pathwidth
• Majority constraints have bounded pathwidth duality

Cited in

(14)

• Majority constraints have bounded pathwidth duality
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• On constraint satisfaction problems below P
• On constraint satisfaction problems below P
• Near unanimity constraints have bounded pathwidth duality
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• Solving order constraints in logarithmic space
• STACS 2004
• Linear Datalog and Bounded Path Duality of Relational Structures
• Recognizing frozen variables in constraint satisfaction problems
• H-coloring dichotomy revisited
• The complexity of constraint satisfaction games and QCSP
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• CSP duality and trees of bounded pathwidth

This page was built for publication: Constraint satisfaction problems in non-deterministic logarithmic space

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