IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Complexity of Regex Crosswords

  • Feb. 22, 2019
  • 2:30 p.m.
  • LeConte 312

Abstract

Regular expression crossword puzzles are similar to everyday crosswords, however the "clues" given are regular expressions. In this talk, I will show that a variant of the puzzle where there are only two clues --- one for the rows and one for the columns --- is NP-complete. In addition, I will discuss a 2-player variant and show using a reduction from TQBF that this is PSPACE-complete.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC