Advances in Computer Science and Engineering
Volume 6, Issue 2, Pages 105 - 114
(May 2011)
|
|
A POLYNOMIAL-TIME REDUCTION FROM THE SAT PROBLEM TO THE GENERALIZED ONE-PERSON LAST AND-FIRST GAME
Chuzo Iwamoto and Yusuke Sumida
|
Abstract:
The last-and-first game is a kind of one-person word-chain game, where a player says noun words which begin with the final letter of the previous word, and words may not be repeated. We will construct a polynomial-time reduction from the 3-SAT problem to the generalized one-person last-and-first game. |
| Keywords and phrases: one-person game, polynomial-time reduction. |
| |
| Number of Downloads: 290 | Number of Views: 637 |
|
