長らく放置していた計算複雑性理論の教科書を読み進める。やっとこの分野の (教科書に載るような) 基本的な部分の全体像がつかめてきて、証明方法なんかも少し頭に馴染んできた。とはいえなんというか、間違って大定理を証明してしまいそうな危うさがまだある。
たとえば、つい NP と co-NP を同じものとして扱ってしまったりする。ある NP (でなくてもいいが) 問題を解く決定性アルゴリズムの計算量下限は対応する co-NP 問題のそれと一致する。それを以って「どっちも計算量クラスは同じじゃん」と一瞬思ってしまう。
専門家に P ?= NP 予想のアンケートを取ると P != NP の方が多数派だそうで、理由の深さは違えど素人も同じ感覚を持っていると思うのだが、 NP ?= co-NP についてはどうなんだろう。
追記:
https://www.scottaaronson.com/papers/pnp.pdf
... On the other hand, we could imagine a world where NP = coNP even though P != NP. In that world, there would always be short proofs of unsatisfiability (or of the nonexistence of cliques, Hamilton cycles, etc.), but those proofs could be intractable to find. A generalization of the P != NP conjecture says that this doesn’t happen:
"short proofs of unsatisfiability" が何を指すのか分からない。「unSAT ∈ NP だとすれば、任意の充足不可能な命題論理式の充足不可能性を簡単に (多項式時間で) 証明できる」と言っているのかな。んんそれは正しいの?