Lecture 36

January 12th, Friday (12:30-14:30)

Intractability

• The problem IS is NP-complete
• Definition of node cover and the NC problem
• NC is NP-complete
• Definition of a directed Hamiltonian circuit and the DHC probem
• DHC is NP-complete
• HC is NP-complete
• TSP is NP-complete

Exercises

• Let \( \Sigma = \{a,b,c\} \). State whether the languages \( L_1 = \{ a^n a^m b^n c^m \; | \; n, m \geq 1 \} \) and \( L_2 = \{ a^n a^n b^n c^n \; | \; n \geq 1 \} \) are context-free (exercise from final exam of June 28th, 2021)
• Let \( L_1 \) be a finite language defined over \( \Sigma = \{0,1\} \). Define \( {\cal P} = \{ L \; | \; L \in {\rm RE}, \; L_1 \cap L \not = \emptyset \}\). State whether \(L_{\cal P}\) is in REC, in RE but not in REC, or else outside of RE (exercise 3.8 from the Exercise collection)
• Let \( L_R \) be a regular language defined over \( \Sigma \), and let \( {\cal P} = \{ L \; | \; L \in {\rm RE}, \; L \cup L_R \not = \Sigma^\ast \}\). State whether the languages \( L_1 = L_{{\cal P}} \) and \( L_2 = \{ enc(M_1, M_2) \; | \; L(M_1) \cup L(M_2) \cup L_R = \Sigma^\ast \} \) belong to REC (exercise from final exam of June 28th, 2021)
• Let \(\Sigma = \{a,b\}\). Assess whether the following languages are CFL (exercise from final exam of January 27th, 2020):
  • \( L_1 = \{ xyx^Ry^R \; | \; x,y \in \Sigma^+ \} \)
  • \( L_2 = \{ xyy^Rx^R \; | \; x,y \in \Sigma^+ \} \)
  • \( L_3 = \{ xyy^Rx^R \; | \; x,y \in \Sigma^+, \; |x| = |y| \} \)

References

• Hopcroft et al., chapter 10