2 Search Results for "Barton, Nick"

Document
DOI: 10.4230/LIPIcs.FUN.2021.7
1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete

Authors: Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Consider n²-1 unit-square blocks in an n × n square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable - a variation of Rush Hour with only 1 × 1 cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical 1 × 2 and horizontal 2 × 1 movable blocks and 4-color Subway Shuffle.
Cite as

Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7,
  author =	{Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi},
  title =	{{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.7},
  URN =		{urn:nbn:de:0030-drops-127681},
  doi =		{10.4230/LIPIcs.FUN.2021.7},
  annote =	{Keywords: puzzles, sliding blocks, PSPACE-hardness}
}
Document
DOI: 10.4230/DagRep.6.1.1
Evolution and Computing (Dagstuhl Seminar 16011)

Authors: Nick Barton, Per Kristian Lehre, and Nisheeth Vishnoi

Published in: Dagstuhl Reports, Volume 6, Issue 1 (2016)

Abstract
This report documents the talks and discussions at the Dagstuhl seminar 16011 “Evolution and Computing”. The seminar brought together several research disciplines studying evolution, including population genetics and mathematical biology, theoretical computer science, and evolutionary computation.
Cite as

Nick Barton, Per Kristian Lehre, and Nisheeth Vishnoi. Evolution and Computing (Dagstuhl Seminar 16011). In Dagstuhl Reports, Volume 6, Issue 1, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{barton_et_al:DagRep.6.1.1,
  author =	{Barton, Nick and Lehre, Per Kristian and Vishnoi, Nisheeth},
  title =	{{Evolution and Computing (Dagstuhl Seminar 16011)}},
  pages =	{1--14},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{1},
  editor =	{Barton, Nick and Lehre, Per Kristian and Vishnoi, Nisheeth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.1.1},
  URN =		{urn:nbn:de:0030-drops-58064},
  doi =		{10.4230/DagRep.6.1.1},
  annote =	{Keywords: Evolution, Evolutionary Computation, Natural Algorithms, Theory of Computation}
}
  • Refine by Author
  • 1 Barton, Nick
  • 1 Brunner, Josh
  • 1 Chung, Lily
  • 1 Demaine, Erik D.
  • 1 Hendrickson, Dylan
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 1 Evolution
  • 1 Evolutionary Computation
  • 1 Natural Algorithms
  • 1 PSPACE-hardness
  • 1 Theory of Computation
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2016
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact