A1 H. Ito

AD [Sch. of Inf. & Eng., Univ. of Electro-Commun., Chofu, Sch. of Inf. [amp ] Eng., Univ. of Electro-Commun., Chofu]

A1 S. Seki

AD [Sch. of Inf. & Eng., Univ. of Electro-Commun., Chofu, Sch. of Inf. [amp ] Eng., Univ. of Electro-Commun., Chofu]

PB iet

T1 Computational complexity of inverse word search problem

JN IET Conference Proceedings

SP 4 .

OP 4 .

AB Word search is a classical puzzle to search for all given words on a given assignment of letters to a rectangular grid (matrix). This problem is clearly in P. The inverse of this problem is more difficult, which asks to assign letters in a given alphabet to a matrix of given size so that every word in a given wordset can be found horizontally, vertically, or diagonally. This problem is in NP; it admits a trivial polynomial-size certificate. We prove its NP-hardness. It turns out to be so even under the following restrictions: 1) the alphabet size is 2 (binary) and 2) all the words to be found are of length at most 2. These results are optimal in the sense that decreasing these bounds 2 to 1 makes the problem be trivially in P.

K1 inverse word search problem

K1 NP-hardness

K1 computational complexity

K1 rectangular grid

K1 trivial polynomial-size certificate

DO https://doi.org/10.1049/cp.2015.0607

UL https://digital-library.theiet.org/;jsessionid=fog9sdjkriaq2.x-iet-live-01content/conferences/10.1049/cp.2015.0607

LA English

SN

YR 2015

OL EN