Single-Player and Two-Player Buttons & Scissors Games

Single-Player and Two-Player Buttons & Scissors Games

We study the computational complexity of the Buttons & Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-complete for C=2 colors but polytime solvable for C=1. Similarly the game is NP-complete if every color is used by at most...

Full description

Bibliographic Details
Main Authors: Burke, Kyle, Gregg, Harrison, Hearn, Robert A., Hoffmann, Michael, Ito, Hiro, Kostitsyna, Irina, Leonard, Jody, Löffler, Maarten, Santiago, Aaron, Schmidt, Christiane, Uehara, Ryuhei, Uno, Yushi, Williams, Aaron, Demaine, Erik D, Hesterberg, Adam Classen
Other Authors: Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format: Article
Language:en_US
Published: Springer 2018
Online Access:http://hdl.handle.net/1721.1/114763
https://orcid.org/0000-0003-3803-5703
https://orcid.org/0000-0002-6053-1167

Internet

http://hdl.handle.net/1721.1/114763
https://orcid.org/0000-0003-3803-5703
https://orcid.org/0000-0002-6053-1167

Similar Items