1
$\begingroup$

How to prove that this crossword puzzle is NP-complete?

  • We have an instance of crosswords in a square grid $G$ ​​of size $m \times m$.

  • We have a set of black boxes $N$.

  • We have a dictionary of words $D \subseteq\Sigma^{\ast}$, where $\Sigma$ is a finite alphabet.

The question is whether there is a way to fill in the white boxes ($G\setminus N$) so that all the horizontal and vertical words belong to $D$. Here we suppose $|\Sigma|\geq 3$.

Also note that the reduction should not create a dictionary that is too large.

$\endgroup$
7
  • $\begingroup$ You can reduce some version of Planar SAT to your problem. It would require some work. $\endgroup$ Feb 8, 2020 at 5:10
  • $\begingroup$ I think it's possible to use 3-SAT here, but how to do it? $\endgroup$
    – tala
    Feb 11, 2020 at 22:12
  • $\begingroup$ Why do you think it’s possible? Somebody told you? $\endgroup$ Feb 11, 2020 at 22:14
  • $\begingroup$ No, I just know that all NP-complete problems get reduced to 3-SAT $\endgroup$
    – tala
    Feb 11, 2020 at 22:19
  • $\begingroup$ Right, but sometimes there isn’t any simple direct reduction. $\endgroup$ Feb 11, 2020 at 22:21

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.