Section outline

  • December 18th, Thursday (14:30-16:30)

    Intractability

    • Polynomial time reduction
    • NP-complete problems and NP-hard problems
    • Boolean expressions

    Exercises

    • Recall that for two strings \( x,w \in \Sigma^\ast \), we say that \(x\) is an infix of \(w\) if we can write \(w = uxv\) for some strings \( u,v \in \Sigma^\ast \). Define \({\cal P} = \{ L \; | \; L \in {\rm RE},\) every string in \( L \) has infix \( 01110\}\) and define \( L_{\cal P} = \{ \mathsf{enc}(M) \; | \; L(M) \in {\cal P} \} \).
      • Use Rice's theorem to show that \(L_{\cal P}\) is not a recursive language
      • Prove that \(L_{\cal P}\) is not in RE
      (exercise from final exam of September 13th, 2023)
    • Let \(L = \{ enc(M_1, M_2) \; | \; L(M_1) \subseteq L(M_2) \} \) with \(M_1, M_2\) TMs. Is \(L\) a recursively enumerable language? (exercise from final exam of January 22nd, 2019)

    References

    • Hopcroft et al., cap. 10