著者

パブルス J.

出版者

日経サイエンス ; 1990-

雑誌

日経サイエンス (ISSN:0917009X)

巻号頁・発行日

vol.42, no.12, pp.60-66, 2012-12

---

答えを見つけるのは難しいかもしれないが答えがあっているかどうかは素早くチェックできる問題(ジグソーパズルのような問題)のことをNP問題,簡単に素早く解ける問題のことをP問題という。「素早く解けるP問題はすべて,答えを素早く確認できるNP問題である」ことが証明されているが,その逆はどうだろうか。