単一2負項を加えたホーン関数
スポンサーリンク
概要
- 論文の詳細を見る
ホーン関数は高々1個の負リテラルを含む主項を持つブール関数である. ホーン関数に2個の負リテラルを含む項を1個(論理和で)加えたブール関数のクラスを考える. このクラスに属す関数は3個の負リテラルを持つ主項を含まないことを示す. また, ホーン関数に2個の負リテラルを含む項を2個加えたブール関数は3個の負リテラルを含む主項を数多く持つ場合があることを示す. 積和標準形で与えられたこのクラスに属す関数のトートロジー問題がP完全であることを示す.
- 社団法人電子情報通信学会の論文
- 2005-03-11
著者
関連論文
- D-1-2 「ストーンヘンジ」の先手必勝性と一般化ストーンへンジのPSPACE完全性(D-1. コンピュテーション,一般セッション)
- 一般化詰将棋問題の指数時間完全性
- 一般化詰将棋問題の指数時間完全性について
- D-1-1 一般化美術館問題のNP完全性(D-1.コンピュテーション,一般講演)
- 単一2負項を加えたホーン関数
- 単一2負項を加えたホーン関数
- 一般化ブロックパズルのPSPACE完全性の別証明 (計算機科学基礎理論の新展開)
- LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集の発行にあたって(LAシンポジウム(計算機科学基礎理論ワークショップ)論文小特集)
- LAシンポジウム(情報基礎理論ワークショップ)論文小特集の発行にあたって(和文論文誌D-I・英文論文誌E-D合同)
- T(G)を計算する新しいアルゴリズム
- T(G)を計算する新しいアルゴリズム
- (4,7)-、(5,6)-マージングネットワークの最小比較器数のコンピュータによる計算 (離散的アルゴリズムと計算量)
- (4, 7)-マージングネットワークと(5, 6)-マージングネットワークの最小比較器数について
- マージングネットワークの下界について
- マージングネットワークの下界の計算について
- マージングネットワークにおけるある下界について(計算量理論の諸相 : その基礎的研究)
- n×n盤面上の将棋の指数時間完全性について