文献

J-GLOBAL ID：201202243961640447   整理番号：12A1052366

完全バイナリー基礎上の公式に対する充足可能性アルゴリズムと平均ケース困難性

A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis

著者 (2件)： SETO Kazuhisa (Kyoto Univ.) ,  TAMAKI Suguru (Kyoto Univ.)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 93(COMP2012 12-25)  ページ： 41-48  発行年： 2012年06月14日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： 著者らは,完全バイナリ基盤上で,Boole論理式の充足可能性に対する中程度指数時間のアルゴリズムを提示する。サイズが高々cnである公式に対して,著者らのアルゴリズムは,ある定数μc>0に対して2^(1-μc)の時間で動く。このアルゴリズムの実行時間分析の副産物として,著者らは,完全バイナリ基盤上での線形サイズの公式に対する強い平均ケースの困難さのアフィンエクストラクタを得る。(翻訳著者抄録)

シソーラス用語： *充足可能性問題 ,  数 ,  論理演算 ,  論理関数 ,  アルゴリズム ,  *NP困難
準シソーラス用語： バイナリー ,  *論理式充足可能性問題

分類 (1件)： 論理代数  (JB03000H)

引用文献 (35件)：

• AJTAI, Miklos. Σ^1_1-formulae on finite structures. Ann. Pure Appl. Logic. 1983, 24, 1, 1-48
• ANDREEV, A. E. On a method for obtaining more than quadratic effective lower bounds for the complexity of π-schemes. Moscow Univ. Math. Bull. 1987, 42, 1, 63-66
• ARVIND, Vikraman. The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems. Proceedings of the 14th Annual International Symposium on Algorithm and Computation (ISAAC), 2003. 2003
• BIERE, A. editor. Handbook of Satisfiability. 2008
• BOURGAIN, Jean. On the construction of affinesource extractors. Geometric and Functional Analysis. 2007, 17, 1, 33-57

タイトルに関連する用語 (6件)： バイナリー ,  基礎 ,  充足可能性 ,  アルゴリズム ,  平均 ,  困難性