導出原理の計算複雑さについて
スポンサーリンク
概要
- 論文の詳細を見る
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
論文 | ランダム
- 113.放射線治療における線量分布の3次元表示について : 治療-5 : 線量分布-1
- 37.コンピュータグラフィックスの医用画像への応用 : 関東・東京合同部会 : 会員研究発表 : 画像管理(III)
- 62.放射線治療における線量分布の3次元表示について : (第1報)CT画像の立体表示について
- 62.放射線治療における線量分布の3次元表示について(第1報) : CT画像の立体表示について(第13回秋季学術大会)
- 33.CT画像を応用した放射線治療計画システム : (ハードウェアの充実について)(関東東京部会)