Computational complexity of inverse word search problem
Computational complexity of inverse word search problem
复制标题
逆词搜索问题的计算复杂度
DOI：
10.1049/cp.2015.0607
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Hiro Ito and Shinnosuke Seki
中科院分区：
文献类型：
--
作者：
N. Fu;A. Hashikura and H. Imai;Hiro Ito and Shinnosuke Seki
单词搜索是一个经典的谜题，用于在矩形网格（矩阵）的给定字母分配上搜索所有给定单词。这个问题在P中很明显。这个问题的逆过程更困难，它要求将给定字母表中的字母分配给给定大小的矩阵，以便可以水平、垂直或对角地找到给定单词集中的每个单词。这个问题是NP问题；它承认一个简单的多项式大小的证书。我们证明了它的NP硬度。即使在以下限制下，结果也是如此：1）字母表大小为 2（二进制）并且 2）要找到的所有单词的长度最多为 2。这些结果是最优的，因为将这些界限 2 减小到 1 使得问题在 P 中变得微不足道。
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.