19 citations · 46 across the 18 of their papers we have counts for
6 papers · 1 filter
Mad Science is Provably Hard: Puzzles in Hearthstone's Boomsday Lab are NP-hard
Michael Hoffmann, Jayson Lynch, Andrew Winslow
We consider the computational complexity of winning this turn (mate-in-1 or "finding lethal") in Hearthstone as well as several other single turn puzzle types introduced in the Boo…
Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect
Jean Cardinal, Erik D. Demaine, David Eppstein +2
We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform…
Verification in Staged Tile Self-Assembly
Robert Schweller, Andrew Winslow, Tim Wylie
We prove the unique assembly and unique shape verification problems, benchmark measures of self-assembly model power, are -hard and contained in $\math…
Intrinsic universality in tile self-assembly requires cooperation
Pierre-Étienne Meunier, Matthew J. Patitz, Scott M. Summers +3
We prove a negative result on the power of a model of algorithmic self-assembly for which it has been notoriously difficult to find general techniques and results. Specifically, we…
Staged Self-Assembly and Polyomino Context-Free Grammars
Andrew Winslow
Previous work by Demaine et al. (2012) developed a strong connection between smallest context-free grammars and staged self-assembly systems for one-dimensional strings and assembl…
Two Hands Are Better Than One (up to constant factors)
Sarah Cannon, Erik D. Demaine, Martin L. Demaine +5
We study the difference between the standard seeded model of tile self-assembly, and the "seedless" two-handed model of tile self-assembly. Most of our results suggest that the two…