高密度深さ2閾値回路のあるクラスに関する充足可能性アルゴリズム

AMANO Kazuyuki; SAITO Atsushi

文献

J-GLOBAL ID：201502212689883776 整理番号：15A0194690

高密度深さ2閾値回路のあるクラスに関する充足可能性アルゴリズム

A Satisfiability Algorithm for Some Class of Dense Depth Two Threshold Circuits

出版者サイト複写サービスで全文入手 {{ this.onShowCLink("http://jdream3.com/copy/?sid=JGLOBAL&noSystem=1&documentNoArray=15A0194690&COPY=1") }}
高度な検索・分析はJDreamⅢで {{ this.onShowJLink("http://jdream3.com/lp/jglobal/index.html?docNo=15A0194690&from=J-GLOBAL&jstjournalNo=U0469A") }}

著者 (2件)： ,
資料名：
巻： E98.D 号： 1 ページ： 108-118 (J-STAGE) 発行年： 2015年
JST資料番号： U0469A ISSN： 1745-1361 資料種別：逐次刊行物 (A)
記事区分：原著論文発行国：日本 (JPN) 言語：英語 (EN)

近年,Impagliazzo他は,cnワイヤを備えた回路クラスである深さ2スパース閾値回路の充足可能性問題に関して,重要なアルゴリズムを構築した。より大きなクラスの回路に関する重要なアルゴリズムを構築した。深さ2閾値回路のボトムレベルにおいて,一方の出力が他方の出力よりも常に大きいまたは等しいならば,2つのゲートは非依存である。依存性を有するゲートがスパースではない回路クラスに関する,重要な充足可能性アルゴリズムを付与した。動機の一つは,多様な回路クラスと,これらクラスに対応する回路充足可能性問題の複雑性との関連性を考察することにあった。他の背景は,Ryan Williamsにとって始められた回路充足可能性アルゴリズムと下界との結合を用いて,TC⁰回路の強下界を証明することであった。(翻訳著者抄録)

, , , , , , , , , ,
, , ,

論理代数 , 論理回路

引用文献 (22件)：

[1] A. Biere, A. Cimatti, E. Clarke, and Y. Zhu, “Symbolic modelchecking without BDDs,” in Tools and Algorithms for the Construction and Analysis of Systems, pp.193-207, 1999.
[2] R.B. Boppana and M. Sipser, “The complexity of finite functions,” in Handbook of theoretical computer science (vol.a), pp.757-804, MIT Press, Cambridge, MA, USA, 1990.
[3] C. Calabro, “The exponential complexity of satisfiability problems,” PhD thesis, University of California, San Diego, 2009.
[4] C. Calabro, R. Impagliazzo, and R. Paturi, “The complexity of satisfiability of small depth circuits,” Parameterized and Exact Computation: 4th International Workshop, IWPEC 2009, Copenhagen, Denmark, Sept. 2009, Revised Selected Papers, pp.75-85, Springer-Verlag, Berlin, Heidelberg, 2009.
[5] A.K. Chandra, L. Stockmeyer, and U. Vishkin, “Constant depth reducibility,” SIAM J. on Comput, vol.13, no.2, pp.423-439, 1984.

, , ,

前のページに戻る