# Computation

Jan 21, 2021

## Lectures from Guochaun Zhang

• Contents:

• 可计算性
• 有效计算性
• 近似算法
• Approximation Algorithms

• Constant Factor
• Polynomial-time Approximation Scheme (PTAS)
• Efficient polynomial-time approximation scheme (EPTAS)
• Fully Polynomial-time Approximation Scheme (FPTAS)
• Absolute
• Complextity Classes

• Expected Polynomial time (EP)
• Zero-error Probabilistic Polynomial time (ZPP)
• Bounded-error Probabilistic Polynomial time (BPP)
• Randomized Polynomial time (RP)
• 单边错误
• Only for dicision langurages.
• NO instances are always rejected
• YES instances are rejected with p < 1.
• co-RP, co-*, …
• Also other classes like co-* .
• Some theorems:
• $\mathrm{NP} = \mathrm{RP}^*$
• $\mathrm{EP} = \mathrm{ZPP}$
• $\mathrm{ZPP}(1 - 1/p(n)) = \mathrm{ZPP}(2^{-q(n)})$
• $\mathrm{RP}(1 - 1 /p(n)) = \mathrm{RP}(2^{-q(n)})$
• Strong NP-Complete
• Unary NP-Complete (一进制下的 NP 完全)
• Turing Machine

• Language (语言)
• ${0,1}^*$
• set of YES instances
• Configuration (格局): $M \in \mathcal{K} × \delta \sum^* × ( \sum^* (\sum\backslash{ \sqcup } )^*e)$
• Exts:
• Multiple tapes
• Two way infinite tape