%0 Electronic Article
%A H. Ito
%+ [Sch. of Inf. & Eng., Univ. of Electro-Commun., Chofu, Sch. of Inf. [amp ] Eng., Univ. of Electro-Commun., Chofu]
%A S. Seki
%+ [Sch. of Inf. & Eng., Univ. of Electro-Commun., Chofu, Sch. of Inf. [amp ] Eng., Univ. of Electro-Commun., Chofu]
%K inverse word search problem
%K NP-hardness
%K computational complexity
%K rectangular grid
%K trivial polynomial-size certificate
%X 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.
%T Computational complexity of inverse word search problem
%B IET Conference Proceedings
%D
%P 4 .-4 .
%I Institution of Engineering and Technology
%U https://digital-library.theiet.org/;jsessionid=d6ocdbppsnht3.x-iet-live-01content/conferences/10.1049/cp.2015.0607
%G EN