別解問題の計算論的複雑さと完全性およびパズルへの応用
という論文を読んだ。http://www-imai.is.s.u-tokyo.ac.jp/~yato/library.htmlより、修士論文。
この著者はスリザーリンクのNP完全性を証明した人。この論文では「別解問題(ASP)」という問題に着目していて、 ASP 完全なパズルについて議論している。別解問題というのは、ある数nに対して「ある問題に対してn個の答えが与えられているときに残りの答えを出す」というような感じの問題。で、 ASP 完全な問題のとき、 n-ASP の決定問題(ある問題とn個の答のセットが与えられたとき、さらに答があるかどうかを判定する問題)が NP 完全になる。論文中ではスリザーリンク、数独、フィルオミノの ASP 完全性の証明が載っている。
パズルは人手で作ることが多いけど、ある問題に対しては解が一意に定まってほしい。ということで、ある問題が与えられたときに解が本当に一意であるかどうかを調べるのが別解問題で、この論文では、仮に答えがわかっていてもほかに別解が存在するかどうかの判定することが本質的に難しくなることを示している。