| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2016-10-21 14:00 SYM-AND2段回路の充足可能性問題に対する厳密アルゴリズム ○脊戸和寿（成蹊大）・玉置 卓（京大）・照山順一（NII）  COMP2016-27 |
|
| 抄録 | （和） | $n$変数論理関数$f:{0,1}^n rightarrow {0,1}$が重み付き対称であるとは，$f(x_1, ldots, x_n)= g(w_0+sum^n_{i=1} w_ix_i)$を満たす関数$g: mathbb{Z} rightarrow {0,1}$と整数$w_0, ldots w_n$が存在することをいう．論理回路の充足可能性問題とは，論理回路$C$が与えられたときに，$C$が1を出力するような入力変数への割当が存在するかを判定する問題である．本報告書では入力制限のない重み付き対称素子(SYM)と論理積素子(AND)で構成される2段論理回路の充足可能性問題を扱う．ただし，対称素子は出力素子にのみ現れる．我々は$n$変数，$m$素子の本問題に対して，$poly(n,m)cdot 2^{n-Omega((n/log m)^{log n/4log (nm)})}$アルゴリズムを提案する．また，我々のアルゴリズムは$n$変数，$O(n^t)$節の最大充足可能性問題を$poly(n^t)cdot 2^{n-n^{1/O(t)}}$で解くことが可能である．このアルゴリズムは任意の定数$k$に対し，$k$最大充足可能性問題を全探索より超多項式時間高速に解く初めてのアルゴリズムである． |
| （英） | A Boolean function $f: bits{n} to bit$ is {em weighted symmetric} if there exist a function $g: mathbb{Z} to bit$ and integers $w_0, w_1, ldots, w_n$ such that $f(x_1,ldots,x_n) = g(w_0+sum_{i=1}^n w_i x_i)$ holds. In this paper, we present algorithms for the circuit satisfiability problem of depth-2 circuits that consist of one weighted symmetric gate at top and a number of AND gates at bottom. Our algorithm runs in time super-polynomially faster than $2^n$ even when the number of gates is super-polynomial and the maximum weight of symmetric gates is nearly exponential. With an additional trick, we give an algorithm for the maximum satisfiability problem that runs in time $poly(n^t) cdot 2^{n-n^{1/O(t)}}$ for instances with $n$ variables, $O(n^t)$ clauses and {em arbitrary} weights. To the best of our knowledge, this is the first moderately exponential time algorithm even for Max $2$SAT instances with arbitrary weights. |
|
| キーワード | （和） | 充足可能性問題 / 回路計算量 / 定数段数回路 / 対称素子 / / / / |
| （英） | Satisfiability / Circuit Complexity / Constant Depth Circuit / Symmetric Gate / / / / | |
| 文献情報 | 信学技報, vol. 116, no. 262, COMP2016-27, pp. 29-34, 2016年10月. | |
| 資料番号 | COMP2016-27 | |
| 発行日 | 2016-10-14 (COMP) | |
| ISSN | Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2016-27 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2016-10-21 - 2016-10-21 |
| 開催地（和） | 東北大学 |
| 開催地（英） | Tohoku University |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2016-10-COMP |
| 本文の言語 | 英語（日本語タイトルあり） |
| タイトル（和） | SYM-AND2段回路の充足可能性問題に対する厳密アルゴリズム |
| サブタイトル（和） | |
| タイトル（英） | An Exact Algorithm for the Satisfiability of Depth-2 SYM-AND Circuits. |
| サブタイトル（英） | |
| キーワード(1)（和/英） | 充足可能性問題 / Satisfiability |
| キーワード(2)（和/英） | 回路計算量 / Circuit Complexity |
| キーワード(3)（和/英） | 定数段数回路 / Constant Depth Circuit |
| キーワード(4)（和/英） | 対称素子 / Symmetric Gate |
| キーワード(5)（和/英） | / |
| キーワード(6)（和/英） | / |
| キーワード(7)（和/英） | / |
| キーワード(8)（和/英） | / |
| 第1著者 氏名（和/英/ヨミ） | 脊戸 和寿 / Kazuhisa Seto / セト カズヒサ |
| 第1著者 所属（和/英） | 成蹊大学 (略称： 成蹊大) Seikei University (略称： Seikei Univ.) |
| 第2著者 氏名（和/英/ヨミ） | 玉置 卓 / Suguru Tamaki / タマキ スグル |
| 第2著者 所属（和/英） | 京都大学 (略称： 京大) Kyoto University (略称： Kyoto Univ.) |
| 第3著者 氏名（和/英/ヨミ） | 照山 順一 / Junichi Teruyama / テルヤマ ジュンイチ |
| 第3著者 所属（和/英） | 国立情報学研究所 (略称： NII) National Institute of Informatics (略称： NII) |
| 講演者 | 第1著者 |
| 発表日時 | 2016-10-21 14:00:00 |
| 発表時間 | 30分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2016-27 |
| 巻番号（vol） | vol.116 |
| 号番号（no） | no.262 |
| ページ範囲 | pp.29-34 |
| ページ数 | 6 |
| 発行日 | 2016-10-14 (COMP) |
[研究会発表申込システムのトップページに戻る]