読者です 読者をやめる 読者になる 読者になる

SATについて考えていた

式の自由変数の数をNとすると、すべての真理値の割り当てはN2通り。式の長さをMとすると、validityの検査はO(M)くらいだろう。N < Mだから、時間計算量は全部でO(M3)???

って、あれぇ???多項式になっちゃった……なんで?(本当は「M3か!そうか確かに多項式じゃないな!」とかトイレの中で納得して、手を洗っているときに思い直して「いやいやいやいや」ってなったりしたわけだけど。)





そんな日曜日。






N2通りが間違い。2N通り。ちゃんとPじゃなくなった。よかった。