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)

Abstract

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

Theory of Computation - Thomas Zeugmann(2007)

Part 1: Formal Languages


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