Computational complexity of inverse word search problem
Computational complexity of inverse word search problem
- Author(s): H. Ito and S. Seki
- DOI: 10.1049/cp.2015.0607
For access to this article, please select a purchase option:
Buy conference paper PDF
Buy Knowledge Pack
IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.
12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015) — Recommend this title to your library
Thank you
Your recommendation has been sent to your librarian.
- Author(s): H. Ito and S. Seki Source: 12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015), 2015 page ()
- Conference: 12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015)
- DOI: 10.1049/cp.2015.0607
- ISBN: 978-1-78561-085-1
- Location: Luoyang, China
- Conference date: 21-24 Aug. 2015
- Format: PDF
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.
Inspec keywords: matrix algebra; computational complexity; search problems
Subjects: Algebra; Computational complexity; Optimisation; Combinatorial mathematics; Combinatorial mathematics; Optimisation techniques; Optimisation techniques; Algebra; Algebra; Algebra, set theory, and graph theory; Combinatorial mathematics
Related content
content/conferences/10.1049/cp.2015.0607
pub_keyword,iet_inspecKeyword,pub_concept
6
6