Section outline

  • December 19th, Thursday (08:30-10:30)

    Intractability

    • Polynomial time reduction
    • NP-complete problems and NP-hard problems
    • Boolean expressions
    • Satisfiability of Boolean expressions and the SAT problem

    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)

    References

    • Hopcroft et al., cap. 10