導出原理の計算複雑さについて
スポンサーリンク
概要
- 論文の詳細を見る
n節のCNF論理式fと関数ω(n)で,次の条件を満たすものが存在することを示す.(i)ω(n)の値はnの多項式時間で計算できる.(ii)ω(n)は,ある定数c>0に対して,Ω(2^<n^c>)である.(iii)fの充足不能性は導出原理によって,ω(n)ステップで証明できるが,ω(n)-1ステップ以下では証明できない.このことを利用して,R(p(n))を充足不能性がp(n)以下で証明できるn節のCNF論理式fの集合とした時,任意の多項式p(n)n-1に対してR(p(n))がNP完全であることが示される.
- 1995-10-27
論文 | ランダム
- 1K02 モジュール融合 : 製品アーキテクチャの解体と再編((ホットイシュー) オープン・イノベーション (1), 第20回年次学術大会講演要旨集I)
- 1B03 技術選択に関するジレンマのマネジメント : ファナックにおけるジレンマの超克(イノベーションのジレンマへの日本型の解(1))
- 日本産業再生とMOT戦略 (特集 実践的MOTの必要条件を問う)
- 産学連携論考--技術の受け手主導の移転パラダイム
- 大学院教育としてのMOT (特集 産業競争力強化とMOT)