LaserTank is NP-Complete

DOI10.1007/978-3-030-43120-4_26MaRDI QIDQ5014691zbMATH OpenOpenAlexFDO

Authors Per Alexandersson, Petter Restadh

Publication date 8 December 2021

Published in Mathematical Aspects of Computer and Information Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1908.05966

zbMATH Keywords

3-SATLaserTankNP-completeness

Mathematics Subject Classification ID

Numerical analysis (65-XX) Computer science (68-XX)

Recommendations

• Lambek calculus is NP-complete
• NP-completeness of the linear complementarity problem
• The Lambek-Grishin Calculus Is NP-Complete
• Tatamibari is NP-complete
• The monotone Lambek calculus is NP-complete
• The STO problem is NP-complete
• NP-completeness of a combinator optimization problem
• The Traveling Beams Optical Solutions for Bounded NP-Complete Problems
• Hashiwokakero is NP-complete
• Shellability is NP-complete

Cites work

• Gaming is a hard job, but someone has to do it!
• Minesweeper is NP-complete.
• Minesweeper may not be NP-complete but is hard nonetheless
• Rush Hour is PSPACE-complete, or ``Why you should generously tip parking lot attendants
• SOKOBAN and other motion planning problems
• Tetris is Hard, Even to Approximate
• The complexity of theorem-proving procedures

Cited in

(1)

• LaserTank is NP-complete

This page was built for publication: LaserTank is NP-Complete

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