はてなキーワード: 「NP」とは
でも、別のパズルは解くのがとても難しいけど、誰かが「これが答えだよ!」って教えてくれたら、その答えが正しいかどうかをすぐに確認できる。
「NP」は、解くのは難しいけど、答えを確認するのは簡単なもの。
たとえば、簡単な算数の問題は「P」に入るけど、すごく難しい迷路を解くのは「NP」に入るかもしれないね。
P対NP問題は、「すべてのNPのパズルも実はPのパズルなのかな?」という質問なんだ。
つまり、解くのが難しいと思っていたパズルも、実は簡単に解ける方法があるのかもしれない、ということを考えているんだよ。
もし、すべてのNPのパズルがPのパズルだとわかったら、今まで難しいと思っていたことが簡単にできるようになるかもしれない。