回路計算量の線形下界に対する計算機支援証明について
スポンサーリンク
概要
- 論文の詳細を見る
近年の計算機の著しい性能向上を受けて,組み合わせ論的問題に対する計算機支援証明の適用可能性が広がっている.本稿では,明示的論理関数に対する回路計算量の線形下界の導出問題を取り上げ,これに対する計算機支援証明を構成する試みについて報告する.まず,この問題に対する証明手法として広く用いられるゲート除去法を,四色定理の証明との類似性についても言及しつつ,より機械的取り扱いが容易となるよう定式化する.次いで,岩間ら[6]による現在最良の線形下界の証明を,計算機支援のもとで再構成する試みを通じて得られた知見について述べる.
- 社団法人電子情報通信学会の論文
- 2006-10-10
著者
関連論文
- 最簡な論理式でNPN同値類の代表のみを生成するアルゴリズム
- 充足割り当て数を最小化/最大化する単調DNF式について
- 可変マージ関数の否定数限定複雑さ (計算モデルとアルゴリズム)
- 連数限定入力に対する否定数限定ソーティング回路
- ブール関数のPTF表現の複雑さについて
- モノポリストゲームのゲーム長(手数)について
- 単項性判定のための論理関数に関する条件
- DS-1-14 ランダム写像による非線形概念の学習の効率化に向けて(DS-1.COMP-NHC学生シンポジウム,シンポジウム)
- マージンを保存するランダム性を限定したプロジェクションとブール空間への埋め込み
- 指数重み閾値関数の多項式重みによる模倣手法の改良
- 指数重み閾値関数の多項式重みによる模倣手法の改良
- 二次論理関数の単調回路計算量について
- 二次論理関数の単調回路計算量について
- 最適なマージングネットワークについて
- 最適なマージングネットワークについて
- 単調論理関数の性質判定アルゴリズムについて
- 単調論理関数間の距離について
- 論理関数のフーリエスペクトルと非線形性の関係
- 決定森の族の計算能力
- 制限付集合に対する包除原理の性質と数え上げ問題への応用
- 決定木における補助ビット問題について
- CC(6)型回路と(MOD3-MOD2)回路における計算の複雑さについて
- 否定数限定論理回路におけるマージングの複雑さ
- 最適なマージングネットワークについて
- 否定素子数限定論理回路における単調論理関数の複雑さ (アルゴリズムと計算の理論)
- マージ関数とソート関数の否定数限定複雑さ
- 完全K分木型組織構造の多階層関係追加モデル
- 連数限定入力に対する否定数限定ソーティング回路
- 回路計算量の線形下界に対する計算機支援証明について
- 最簡な論理式だけを生成するアルゴリズム(セッション1)
- P vs. NP問題 : 解決へのはるかな道(理論計算機科学の最新動向)
- 近似法のサイズ限定モデル
- サイズ限定モデルに基づく近似法による単調複雑さの下界
- ブール関数のフーリエ変換とその応用
- 単調論理回路計算量vs.論理回路計算量
- クリーク関数の否定数限定複雑さ
- 否定素子数限定論理回路における単調論理関数の複雑さ
- 論理関数の複雑さと近似演算(計算理論とその応用)
- 論理関数の複雑さと近似演算
- 論理関数の複雑さと近似演算
- 単調論理関数と擬似補関数に対する近似モデル(計算モデルと計算の複雑さに関する研究)
- 否定制約のもとでのクリーク関数の複雑さに対する指数関数の下界
- 単調論理関数と擬似補関数に対する近似モデル
- 非単調論理回路に対する Razborov の近似モデルの構造
- 制限付回路モデルに対するRazborovの近似法の適用
- k-限定独立性に基づいたDNFの近似アルゴリズム