光阴冢 赛博空间的自留地

Computation

Aug 16, 2020  

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