Section outline

  • January 10th, Wednesday (12:30-14:30)

    Intractability

    • Boolean expressions
    • Satisfiability of Boolean expressions and the SAT problem
    • Coding for Boolean expressions
    • Cook's theorem (proof of first part only)
    • Normal forms for Boolean expressions
    • CSAT problem and 3SAT problem
    • Definition of independent set and the IS problem
    • The problem IS is NP-complete

    Exercises

    • 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., cap. 10