Section outline

  • January 9th, Tuesday (12:30-14: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

    References

    • Hopcroft et al., chapter 10