* Circuit Lower Bounds for Merlin-Arthur Classes - Rahul Santhanam(2007)[#c26795e9]

[[Complexity Zoo:http://qwiki.stanford.edu/wiki/Complexity_Zoo]]: 計算クラスの定義まとめ

Domain: 連結開集合(切れ目がなく,縁を含まない)

Integral domain: 整域(ab = 0 のとき a = 0 か b = 0 に決まっているような集合)

* Trading Group Theory for Randomness - Laszlo Babai(1985) [#c0ef2f12]

** Abstract [#gb94ff09]

[[nilpotent group:http://ja.wikipedia.org/wiki/%E7%BE%A4%E8%AB%96]]: べき零群

[[matrix group:http://ja.wikipedia.org/wiki/%E6%AD%A3%E5%89%87%E8%A1%8C%E5%88%97]]: 行列群(線形代数群)

[[finite simple group:http://d.hatena.ne.jp/keyword/%CD%AD%B8%C2%C3%B1%BD%E3%B7%B2]]: 有限単純群

[[random oracle:http://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%82%AA%E3%83%A9%E3%82%AF%E3%83%AB]]: ランダムオラクル(全ての入力を値域内のランダムな出力にマッピングする関数)

[[discrete logarithm problem:http://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E5%AF%BE%E6%95%B0%E5%95%8F%E9%A1%8C]]: 離散対数問題

black box group: ブラック・ボックス群?

Papadimitriou's games against nature: ?

finite level: ?

''Merlin is the nondeterministic player and Arthur is the random player.''

Solovay-Strassen: Solovay-Strassenテスト(素数判定法)

user vs. expert games - Goldwasser, Micali and Rackoff

** 1. Introduction [#jfc1d66c]

*** 1.1. Randomness vs. mathematical intractability: a tradeoff [#c02c0dc6]

expanding graph:

*** 1.2. Matrix groups [#s072d6d0]



* Theory of Computation - Thomas Zeugmann(2007) [#x642e472]

** Part 1: Formal Languages [#y98e3622]


Front page   New List of pages Search Recent changes   Help   RSS of recent changes