http://iet.metastore.ingenta.com
1887

Algebra

More general concepts than this:

1-1 of 1 results

Filter by subject:

< Any subject

  • Physics [1]
  • General [1]
  • Mathematical methods in physics [1]
  • Algebra, set theory, and graph theory [1]
  • Electrical and electronic engineering [1]
  • General topics, engineering mathematics and materials science [1]
  • Engineering mathematics and mathematical techniques [1]
  • Algebra [1]
  • Combinatorial mathematics [1]
  • Optimisation techniques [1]
  • See more See less

Filter by content type:

Filter by publication date:

< Any publication date

  • 2015 [1]

Filter by author:

< Any author

Computational complexity of inverse word search problem
Author(s): H. Ito, S. Seki
Source: 12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015), 2015, p. 4 . - 4 .
Type: ConferencePaper
+ Show details - Hide details

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.

Add to favourites
Export citations
Items per page 20 | 50 | 100
Print this page
This is a required field
Please enter a valid email address