# Are regex crosswords NP-hard?

I was fooling around the other day on this website: http://regexcrossword.com/ and it got me wondering what the best way to solve it was.

Can you solve the following problem in polynomial time or is it NP-hard?

Given an NxM grid with N regular expressions for the columns and M for the rows, find any solution to the grid such that all the regular expressions are satisfied, or say that no solution exists.

• Haven't looked at the site yet, but questions with Regexes tend to be PSPACE complete, a class which is at least as hard as NP Sep 19, 2014 at 21:54
• @jmite Guessing strings that fit some regular expressions is "easy" as in that we don't have to derive some global property of the regular expression. In fact, I think the problem is in NP (see comment below FrankW's answer.)
– Raphael
Sep 22, 2014 at 6:21

The problem is NP-hard.

We show this by reducing vertex cover:

Given a graph $G=(V,E)$ and a threshold $k$, is there a subset $V' \subseteq V$ of cardinality at most $k$, so that each edge in $E$ is incident to at least one node in $V'$?

We translate this into a regex crossword with $|E|+1$ columns and $|V|$ rows as follows:

All columns, except for the first, correspond to an edge. They get a regex $0^*1(0|1)^*$.

All rows correspond to a vertex. They get a regex that allows to write either

• a $1$ in the first column and each column corresponding to an edge incident to that node and zeroes in all other columns, or

• $0^*$

Finally, the first column counts the size of the vertex cover. It gets a regex, that allows for at most $k$ ones.

The correspondence between solutions to the regex crossword and vertex covers should be obvious.

Example:

Find a vertex cover of size 2 for the following graph: $V_A = 0^* \big| 10110$

$V_B = 0^* \big| 11101$

$V_C = 0^* \big| 10011$

$V_D = 0^* \big| 11000$

$Counter = 0^* \big| 0^*10^* \big| 0^*10^*10^*$

$E_1 = 0^*1(0|1)^*$

$E_2 = 0^*1(0|1)^*$

$E_3 = 0^*1(0|1)^*$

$E_4 = 0^*1(0|1)^*$

Lastly, you can set up the "crossword" so that $V_A$ through $V_D$ are the top regexes and $Counter$ and $E_1$ through $E_4$ are the left side regexes.

Solving this regex crossword give you a vertex cover of size 2 for nodes $V_A,V_B$ or $V_C,V_B$.

If we change k to be 1 and $Counter$ to be $0^* \big| 0^*10^*$ as another example, the regex crossword is impossible to solve because there is no vertex cover of size 1.

• Since we can a) compute polynomially sized NFA for the regular expressions as well as guess b) the solution and c) (linearly sized) computations of all the NFA and d) verify (in polynomial time) that the computations fit the guessed words, the problem is also in NP.
– Raphael
Sep 22, 2014 at 6:20

The question remains NP-complete even when all the regular expressions are equal. http://arxiv.org/abs/1411.5437