Campus Event Calendar
Event Entry
New for: D3
What and Who
Scrabble is PSPACE-complete
Karolina Soltys
Paris, Warsaw
Talk
Last name has a Polish l, \l in LaTeX, but I don't know how to typeset it.
AG 1, AG 3, AG 5, SWS, AG 4, RG1, MMCI
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Thursday, 11 November 2010
13:00
30 Minutes
E1 4
3rd floor rotunda
Saarbrücken
Abstract
We study the computational complexity of the game of
Scrabble. We prove the PSPACE-completeness of a certain natural model
of the game, showing NP-completeness of Scrabble solitaire game as an
intermediate result.
Scrabble. We prove the PSPACE-completeness of a certain natural model
of the game, showing NP-completeness of Scrabble solitaire game as an
intermediate result.
Contact
Benjamin Doerr
--email hidden
passcode not visible
logged in users only
Benjamin Doerr, 11/09/2010 20:19 -- Created document.