ETH lower bounds for n-queens: time waits for nobody

DOI10.1007/978-3-031-98740-3_21MaRDI QIDQ6876389zbMATH OpenFDO

Authors MIT Hardness Group, Erik D. Demaine, Timothy Gomez, Markus Hecher, Meryl Zhang

Publication date 13 January 2026

Full work available at URL https://doi.org/10.1007/978-3-031-98740-3_21

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05) Combinatorial games (91A46) Algorithmic game theory and complexity (91A68)

Cites work

• A dynamic programming solution to the n-queens problem
• A simplified NP-complete satisfiability problem
• Complexity of n-queens completion
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• scientific article; zbMATH DE number 3421895 (Why is no real title available?)
• On the complexity of k-SAT
• On the hardness of counting problems of complete mappings.
• On unique graph 3-colorability and parsimonious reductions in the plane
• The Seventh Answer Set Programming Competition: Design and Results

This page was built for publication: ETH lower bounds for \(n\)-queens: time waits for nobody

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