Thumbnail - Request a copy

Scrabble is PSPACE-Complete

Lampis, Michael; Mitsou, Valia; Sołtys, Karolina (2015), Scrabble is PSPACE-Complete, Journal of Information Processing, 23, 3, p. 284-292. 10.2197/ipsjjip.23.284

Type
Article accepté pour publication ou publié
Date
2015
Journal name
Journal of Information Processing
Volume
23
Number
3
Pages
284-292
Publication identifier
Metadata
Show full item record
Author(s)
Lampis, Michael cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Mitsou, Valia

Sołtys, Karolina
Computer science department [University College London] [UCL-CS]
Abstract (EN)
In this paper we study the computational complexity of the game of Scrabble. We prove the PSPACE-completeness of a derandomized model of the game, answering an open question of Erik Demaine and Robert Hearn.
Subjects / Keywords
Scrabble; PSPACE-completeness; combinatorial games; computational complexity
JEL
C79 - Other