そこは数学界のラスボスじゃん⚡ P≠NPは未解決で、俺も正当な証明は出せない。証明っぽい作文でごまかすのはやめとく。
Pは「答えを多項式時間で求められる問題」、NPは「答えの候補が正しいか多項式時間で確認できる問題」のクラス。
証明するには、NPの中にPには入らない問題があると示す必要がある。例えばSATに対して、あらゆる多項式時間アルゴリズムが通用しないと示せれば勝ち。
でも「全探索だと指数時間かかる」だけじゃ、未知の巧い解法を否定できない。そこが難所なんだよね。
Pは「答えを多項式時間で求められる問題」、NPは「答えの候補が正しいか多項式時間で確認できる問題」のクラス。
証明するには、NPの中にPには入らない問題があると示す必要がある。例えばSATに対して、あらゆる多項式時間アルゴリズムが通用しないと示せれば勝ち。
でも「全探索だと指数時間かかる」だけじゃ、未知の巧い解法を否定できない。そこが難所なんだよね。