平成２５年度 第１回領域会議
| 開催日時 | 2013年 6月13日（木）～ 6月14日（金） |
|---|---|
| 開催場所 | 京都大学 6月13日 午前: 総合研究4号館 1階 共通2 6月13日 午後: 総合研究8号館 3階 Sホール 6月14日 終日: 総合研究7号館 1階 情報2講義室 |
| プログラム | ||
|---|---|---|
| 6月13日 |
[09:00-09:30] 領域の方向性：渡辺領域代表，事務局連絡 |
|
| [09:30-10:15] A01班Slides，A02班 Slides，A03班 Slides |
休憩（15分） | |
| [10:30-11:15] B01班 Slides，B02班 Slides，B03班 Slides |
||
| [11:15-12:00] C01班 Slides，C02班 Slides，C03班 Slides |
||
| 昼休み（60分） | ||
| [13:00-13:15] 公募研究班 Skip Jordan （北海道大学） Slides |
||
| [13:15-13:30] 公募研究班 宇野 裕之 （大阪府立大学） Slides |
||
| [13:30-13:45] 公募研究班 安永 憲司 （金沢大学） Slides |
||
| [13:45-14:00] 公募研究班 泉 泰介 （名古屋工業大学） Slides |
||
| [14:00-14:15] 公募研究班 塩浦 昭義 （東北大学） Slides |
休憩（15分） | |
| [14:30-14:45] 公募研究班 森山 園子 （東北大学） Slides |
||
| [14:45-15:00] 公募研究班 山中 克久 （岩手大学） Slides |
||
| [15:00-15:15] 公募研究班 伊藤 健洋 （東北大学） Slides |
||
| [15:15-15:30] 公募研究班 永田 賢二 （東京大学） Slides |
||
| 休憩、およびポスターセッション準備（30分） | ||
| [16:00-18:00] ポスターセッション A01班、A02班、A03班、B01班、B02班、B03班、C01班、C02班、C03班， Skip Jordan（北大），宇野 裕之 (府立大)，安永 憲司 (金沢大)， 泉 泰介 (名工大)， 塩浦 昭義 (東北大)，森山 園子 (東北大)， 山中 克久 (岩手大)，伊藤 健洋 (東北大)，永田 賢二 (東大) |
||
| [19:00- ] 懇親会 | ||
| 6月14日 | [13:00-13:50] Circuit Satisfiability Abstract Slides |
脊戸 和寿（電通大） |
| 休憩（15分） | ||
| [14:05-14:55] 非平衡な再帰関数の計算限界 Abstract Slides |
上野 賢哉（京大） | |
| 休憩（15分） | ||
| [15:10-16:00] 論理回路の出力パターン数とその応用 Abstract Slides |
内澤 啓（山形大） | |
講演概要
Circuit Satisfiability by 脊戸 和寿（電通大）
Circuit Satisfiability (CktSAT)とは与えられた論理回路の出力が1になる入力割当が存在するかどうかを判定する問題である．これは有名なNP完全問題の1つであり，入力変数の多項式時間では解けそうにない．それどころか，一般の多項式サイズの回路が与えられるとその充足可能性判定には，2^n時間必要であると思われている．2010年，Ryan WilliamsはCktSATが2^nよりも超多項式的に高速にとけるなら，NEXPが多項式サイズの回路をもたないことを示した．(NEXP not in P/poly) さらに，ある特定の回路クラスCに制限したCktSAT (C-SAT)が同じように高速にとけるなら，NEXPが多項式サイズのクラスCの回路をもたないことも示している．(NEXP not in C) これ以降，CktSATに対する研究は加速し，様々なC-SATに対するアルゴリズムが開発された．現時点でCktSATのアルゴリズムの開発によって計算量クラスの分離に成功したのは，Ryan WilliamsのNEXP not in ACC0のみであるが，多くのC-SATの結果に付随して，Average Case HardnessやCorrelation Boundが示されている．これは一種の計算限界を示すものである．本発表では，一連のCktSATの結果を紹介し，今後の展開について述べる．
非平衡な再帰関数の計算限界 by 上野 賢哉（京大）
再帰的に定義された論理関数に対して，論理式サイズ下界を証明する方法として量子敵対者法を説明し，再帰が非平衡な場合への適用を考えるとともに，下界証明に対する一般的な証明限界について議論する.
論理回路の出力パターン数とその応用 by 内澤 啓 (山形大)
論理回路とは，AND素子やOR素子などの論理素子を基本素子とする組合せ回路である．入力が与えられた時に論理回路が行う計算は，回路を構成する各素子の出力値の組合せ，即ち，出力パターンとして表現できる．ここで，ある回路に現れる出力パターンの種類の総数を，その回路の出力パターン数と呼ぶ．本講演では，この回路の出力パターン数を解析することによって得られる論理回路の下界や，その他の応用について述べる．