@ARTICLE{
iet:/content/conferences/10.1049/cp.2015.0607,
author = {H. Ito},
affiliation = {[Sch. of Inf. & Eng., Univ. of Electro-Commun., Chofu, Sch. of Inf. [amp ] Eng., Univ. of Electro-Commun., Chofu]},
author = {S. Seki},
affiliation = {[Sch. of Inf. & Eng., Univ. of Electro-Commun., Chofu, Sch. of Inf. [amp ] Eng., Univ. of Electro-Commun., Chofu]},
keywords = {inverse word search problem;NP-hardness;computational complexity;rectangular grid;trivial polynomial-size certificate;},
language = {English},
abstract = {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.},
title = {Computational complexity of inverse word search problem},
journal = {IET Conference Proceedings},
year = {2015},
month = {January},
pages = {4 .-4 .(1)},
publisher ={Institution of Engineering and Technology},
url = {https://digital-library.theiet.org/;jsessionid=29dsqcsw1vgb3.x-iet-live-01content/conferences/10.1049/cp.2015.0607}
}