光阴冢

We make choices and life has a way of making us pay for them.

Computation

Nov 29, 2019  

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
      • Multiheads
      • 2D-tape
  • PCP-System

    • In computational complexity theory, the PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits). (From Wikipedia)
    • PCP 和不可计算性
    • PCP 和 Gap Technique