Section outline

  • December 17th, 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

    Exercises

    • Let \(L_1\) and \(L_2\) be recursive languages. Is \(L_1 L_2\) a recursive language? (exercise from final exam of January 22nd, 2019)
    • 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