Introduction to Reduction Proofs

Return to List of Lectures

Previous Lecture

• Presentations
  • Optionally present for ca 15 minutes on some unsolvable problem (or other topic with permission)
  • Handout
• Questions?
• Reduction Proofs
  • Section 5.1 (and introduction to chapter 5)
    • Reduction = converting problem into one easier to solve
      • But beware: if the problem you convert from is provably hard in some sense, then the one you convert to can’t be significantly easier without contradicting that proof
    • e.g., show acceptance reduces to halting, but acceptance isn’t decidable so halting isn’t decidable either
    • Other examples
      • Does Turing machine accept regular language?
      • Also does Turing machine accept context free language?
      • Rice’s theorem mentioned
  • Examples
    • Is L(M) context free?
      • Look at proof for REGULAR_TM, replace “regular” with “context free,” but how?
      • Assume FTSOC that C decides CFL_TM
      • But with C you can decide A_TM as follows:
        

        ATM( M, w )
            construct M2(x) as
                1. if x is of the form anbncn accept
                2. otherwise
                    run M on w
                    if M accepts w, accept
                    otherwise, reject
            run C on M2
            if C accepts M2, accept, otherwise reject

  • Problem set
• Next
  • More reduction practice
  • No reading

Next Lecture