Title: Theory / Unimportant / CS / Fundamental / Complexity / Complexity Arora Barak/{ / Randomized computation
Tags: fromMath mathToDef automaticImplies hasSeenConjDef mathToSee

Definition: The random variable corresponding to the value \(M\) writes at the end of this process.
Page: 125
Chapter: 7
Section: 1
Variables: \(M\) a probabilistic TM.
\(x\) an input.
Notation: \(M(x)\)
Kind: Def

Definition: 1 if \(x\in L\) and 0 otherwise
Page: 125
Chapter: 7
Section: 1
Variables: \(L\subseteq\{0,1\}^*\) and \(x\in \{0,1\}^*\)
Notation: \(L(x)\)
Index: 2
Kind: Def

Definition: The class of languages \(L\) accepted by a PTM \(T\) halting in time \(T\), outputting the correct answer with probability at least \(2/3\).
Page: 125
Chapter: 7
Section: 1
Variables: \(T:\mathbb N\to\mathbb N\)
Notation: \(\mathbf{BPTIME}(T(n))\)
Index: 2
Kind: Def

Name: The language accepted by \(M\)
Definition: The set of words \(x\) such that \(\text{Pr}[M(x)=L(x)]\ge 2/3\).
Page: 125
Chapter: 7
Section: 1
Variables: \(M\) a PTM.
Index: 2
Kind: Def

Definition: \(\cup_c\mathbf{BPTIME}(n^c)\).
Page: 125
Chapter: 7
Section: 1
Notation: \(\mathbf{BPP}\)
Index: 2
Kind: Def

Definition: The set of languages \(L\) accepted by a RTM \(M\), halting in time \(T(n)\) such that \(x\in L\implies Pr[M(x)=1]\ge2/3\) and \(x\not\in L\implies Pr[(x)=0]=1\).
Page: 131
Chapter: 7
Section: 3
Variables: \(T:\mathbb N\to\mathbb N\).
Notation: \(\mathbf{RTIME}(T(n))\)
Index: 6
Kind: Def

Definition: \(\bigcup_{c\in\mathbb N}\mathbf{RTIME}(n^c)\).
Page: 131
Chapter: 7
Section: 3
Notation: \(\mathbf{RP}\)
Index: 6
Kind: Def

Definition: \(\{0,1\}^*\setminus L\) for \(L\in\mathbf{RP}\).
Page: 131
Chapter: 7
Section: 3
Notation: \(\mathbf{coRP}\)
Index: 6
Kind: Def

Smaller0: \(\mathbf{RP}\)
Greater0: \(\mathbf{NP} \)
Page: 131
Chapter: 7
Section: 3
Index: 6
Kind: Def
Smaller to greater: \(\subseteq\)
Greater to smaller: \(\supseteq\)

Definition: The class of languages accepted by a RTM accepting in expected time \(T(n)\), with probability of error 0.
Page: 131
Chapter: 7
Section: 3
Variables: \(T:\mathbb N\to\mathbb N\)
Notation: \(\mathbf{ZTIME}(T)\)
Kind: Def

Definition: \(\bigcup_{c\in\mathbb N}\mathbf{ZTIME}(n^c)\)
Page: 131
Chapter: 7
Section: 3
Notation: \(\mathbf{ZPP}\)
Index: 7, 8
Kind: Def, Theo
Definition2: \(\mathbf{RP} \cap \mathbf{coRP}\)

Smaller0: \(L\) is accepted by a PTM \(M\) such that for every \(x\in\{0,1\}^*\), \(Pr[M(x)=L(x)]\ge1/2+|x|^{-c}\),
Greater0: for every constant \(d>0\) there exists a polynomial-time PTM \(M'\) such that for every \(x\in\{0,1\}^*\) \(Pr[M'(x)=L(x)]\ge1-2^{-|x|^d}\)
Page: 132
Chapter: 7
Section: 4
Variables: \(L\subseteq\{0,1\}^*\)
Index: 10
Kind: Theo

Question: All coins are
Answer: equivalent, for the expressivity of RTM
Page: 135
Chapter: 7
Section: 4.3
Index: 13
Kind: Lem

Smaller0: \(\mathbf{BPP} \)
Greater0: \(\mathbf{P_{/poly} } \)
Page: 136
Chapter: 7
Section: 5
Index: 14, 15
Kind: Theo
Smaller to greater: \(\subseteq\)
Greater1: \(\Sigma_2^p\cap\Pi_2^p\)
Greater to smaller: \(\supseteq\)
Connect Greater0: \(\cap \)

Q: [...]. It is [property].
A: There is a probabilistic TM \(M\) such that for every \(x\in\{0,1\}^*\), \(Pr[B(M(x))=C(x)]\ge2/3\); not transitive
Page: 138
Chapter: 7
Section: 5
Variables: \(B,C\) two languages.
Index: 16
Kind: Def
Name: \(B\) reduces to language \(C\) under a randomized polynomial time reduction
Notation: \(B\le_r C\)

Name: \(\mathbf{BPL}\) and \(\mathbf{RL}\)
Definition: \(\mathbf{BPP}\) and \(\mathbf{RP}\), restricted to log-space
Page: 139
Chapter: 7
Section: 6
Index: 18, 19
Kind: Def, Theo
Example: UPATH

Smaller0: \(\mathbf{BPL} \)
Greater0: \(\mathbf{SPACE(\log^{3/2}n)} \)
Page: 139
Chapter: 7
Index: 19
Kind: Theorem
Smaller to greater: \(\subseteq\)
Greater to smaller: \(\supseteq\)

Name: Probabilistic Turing machine (PTM)
Definition: A Turing machine with two transitions \(\delta_0,\delta_1\) at each transition, each function is used with probability 0.5.
Page: 125
Chapter: 7
Section: 1
Kind: Def
Definition2: A Turing machine with two inputs, where the second is a random string