文献

J-GLOBAL ID：201902225614817720   整理番号：19A1531876

重み付き対称ゲートを持つ有界深さ回路:充足可能性,下界および圧縮【JST・京大機械翻訳】

Bounded depth circuits with weighted symmetric gates: Satisfiability, lower bounds and compression

著者 (4件)： Sakai Takayuki (Oki Electric Industry Co., Ltd., Japan) ,  Seto Kazuhisa (Seikei University, Japan) ,  Tamaki Suguru (University of Hyogo, Japan) ,  Teruyama Junichi (University of Hyogo, Japan)
資料名： Journal of Computer and System Sciences  (Journal of Computer and System Sciences)
巻： 105  ページ： 87-103  発行年： 2019年 
JST資料番号： B0861A  ISSN： 0022-0000  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Boole関数f:{0,1}n→{0,1}は,関数g:Z→{0,1}と整数w0,w1,...のように,f(x1,...,xn)=g(w0+Σi=1nwixi)が保持されると対称的に重み付けされる。本論文では,AND,OR,NOTゲートおよび限られた数の重み付け対称ゲートを有する有界深さ回路の回路充足可能性問題のためのアルゴリズムを提示した。著者らのアルゴリズムは,ゲート数が超多項式であり,対称ゲートの最大重みがほぼ指数関数である場合でも,2nよりも時間的に超多項式的に速く走る。特別な事例として,n変数とO(nt)節を持つインスタンスに対して,時間ポリ(nt)2n-n1/O(t)を実行する最大充足可能性問題のアルゴリズムを得た。著者らのアルゴリズムの解析を通して,そのような回路の大多数投票に対して,そのような回路および最悪ケース下限に対する平均ケース下限および圧縮アルゴリズムを示した。Copyright 2019 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 線形性 ,  重みづけ ,  Boole関数 ,  CASE ,  アルゴリズム ,  *対称性 ,  投票 ,  充足可能性問題 ,  多項式 ,  指数関数 ,  アルゴリズム解析 ,  *下界 ,  *有界

著者キーワード (7件)： 打ち込まれた力 ,  回路の複雑さ ,  最大充足可能性 ,  制限 ,  収縮 ,  対称関数 ,  線形しきい値関数

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (5件)： 対称 ,  ゲート ,  有界 ,  充足可能性 ,  下界