202531301

計算複雑性理論はとにかく素朴な疑問が未解決問題で、そばを掠めるたびに驚く。

これらは同じ性質の難しさなんだろうか。でも、少なくとも P != NP を仮定したら大半の問題が解けるという話は目にしない (もちろんそういう問題もたくさんあるとは思うけれど) ので、そんなに単純 (?) な話ではないのだろうな。