scientific article; zbMATH DE number 2086639

MaRDI QIDQ4737175zbMATH OpenFDO

Authors Robert A. Hearn, Erik D. Demaine

Publication date 11 August 2004

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

zbMATH Keywords

nondeterministic model of computation

Mathematics Subject Classification ID

Logic in computer science (03B70) Logic programming (68N17) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Recommendations

• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• Parameterized complexity of graph constraint logic
• \(1\times 1\) Rush Hour with fixed blocks is PSPACE-complete
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete

Cited in

(20)

• The complexity of Snake and undirected NCL variants
• SOKOBAN and other motion planning problems
• Turing Tumble is P(SPACE)-complete
• PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation
• \textsc{Pull} and \textsc{PushPull} are PSPACE-complete
• scientific article; zbMATH DE number 4037175 (Why is no real title available?)
• scientific article; zbMATH DE number 4043254 (Why is no real title available?)
• scientific article; zbMATH DE number 2002586 (Why is no real title available?)
• The kissing problem: how to end a gathering when everyone kisses everyone else goodbye
• \textsc{Snowman} is \(\mathsf{PSPACE}\)-complete
• Parameterized complexity of graph constraint logic
• On the Symbolic Computation of the Hardest Configurations of the RUSH HOUR Game
• Fixed-parameter algorithms for graph constraint logic
• Fixed-parameter algorithms for graph constraint logic
• Non-finite axiomatisability results via reductions: CSP parallel composition and CCS restriction
• Walking through doors is hard, even without staircases: proving PSPACE-hardness via planar assemblies of door gadgets
• \(1\times 1\) Rush Hour with fixed blocks is PSPACE-complete
• Defying gravity and gadget numerosity: the complexity of the Hanano puzzle and beyond
• A generalized matching reconfiguration problem
• Reconfiguration of unit squares and disks: PSPACE-hardness in simple settings

This page was built for publication:

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