SATについて考えていた

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

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





そんな日曜日。






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