Circuit Lower Bounds for Merlin-Arthur Classes - Rahul Santhanam(2007)

Complexity Zoo: 計算クラスの定義まとめ

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

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

Trading Group Theory for Randomness - Laszlo Babai(1985)


nilpotent group: べき零群

matrix group: 行列群(線形代数群)

finite simple group: 有限単純群

random oracle: ランダムオラクル(全ての入力を値域内のランダムな出力にマッピングする関数)

discrete logarithm problem: 離散対数問題

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

1.1. Randomness vs. mathematical intractability: a tradeoff

expanding graph:

1.2. Matrix groups

Representation Theory

harmonic analysis: ?

permutation group: 置換群 = 対象群(symmetric group)

integral matrix: 行列積分?

number theoretic: 数論

Monte Carlo method: モンテカルロ法

PP: Probabilistic Polynomial time

BPP: Bounded-error Probabilistic Polynomial time

Theory of Computation - Thomas Zeugmann(2007)

Part 1: Formal Languages

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