13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – jmite Sep 19 '14 at 21:54
  • 1
    $\begingroup$ @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.) $\endgroup$ – Raphael Sep 22 '14 at 6:21
11
$\begingroup$

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:

https://i.imgur.com/TY6sjjV.png

$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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Raphael Sep 22 '14 at 6:20
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.