2007-07-24 [長年日記]
λ. トートロジー判定問題の計算量
(古典命題論理の)充足可能性問題(SAT)がNP完全なので、その補問題である(古典命題論理の)トートロジー判定問題はco-NP完全になるそうだ。 ということは証明可能であることを検査する Wang's Algorithm も計算量は co-NP ということか。
NP や co-NP のような計算量って、あまり興味がなかったのだけど、実は結構身近な話だったんだな。
[ツッコミを入れる]
日々の流転
プロフィール
カレンダー
| 前 | 2007年 7月 |
次 | ||||
| 日 | 月 | 火 | 水 | 木 | 金 | 土 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 | 31 | ||||