Section outline

  • December 18th, Wednesday (10:30-12:30)

    Intractability

    • Intractable problems
    • Time complexity for a TM
    • Polynomial time algorithms
    • Complexity analysis for a TM
    • Nondeterministic polynomial time algorithms
    • Polynomial time reduction
    • NP-complete problems and NP-hard problems

    Exercises

    • Prove the truth or falsehood of the following statements (exercise from final exam of January 27th, 2020)
      • Given \(L_1\) and \(L_2\) not in REG, the language \(L_1 \cap L_2\) cannot be in REG
      • Given \(L_1\) in REG and \(L_2\) in CFL, the language \(L_1 L_2\) is in REG
      • Given \(L_1\) in CFL, the language \(\overline{L_1}\) cannot be in CFL
      • Given \(L_1\) and \(L_2\) in CFL, the language \(L_1 \cap L_2\) is in REC
    • Let \(w\) be a string in \(\{0,1\}^\ast\). Define \({\cal P} = \{ L \; | \; L \in {\rm RE}, \; w \in L \} \) and define \( L_{\cal P} = \{ \mathsf{enc}(M) \; | \; L(M) \in {\cal P} \} \). Is \(L_{\cal P}\) a recursive language? Is \(L_{\cal P}\) a recursively enumerable language? (exercise from final exam of February 13th, 2019)

    References

    • Hopcroft et al., chapter 10