(Possibly Imperfect) Proof #5

You should work on this problem individually (no partners) and submit your answers as a PDF file to Gradescope.
Read the below proof carefully and then answer the questions at the end.

Problem: Show that NP is closed under INTERSECTION.

Claim: The class NP is closed under INTERSECTION.

Proof:

Let A, B ∈ NP and let MA, MB be nondeterministic Turing machines that decide languages A, B in polynomial times fA(n), fB(n) respectively.

Define a nondeterministic Turing machine M =

"On input w:

1. Simulate MA on w. If the MA simulation ends in a rejecting state then halt and reject.
2. Simulate MB on w. If the MB simulation ends in a rejecting state then halt and reject
3. Halt and accept."

Since MA and MB are deciders, they will always halt, either accepting or rejecting. For machine M, step (1) takes fA(n) time, step (2) takes fB(n) time, and step (3) takes constant time. The total runtime for machine M is fA(n) + fB(n) + constant, which is a polynomial runtime. Thus, M is a nondeterminstic Turing machine that decides the intersection of two arbitrary NP languages in polynomial time and, hence, NP is closed under INTERSECTION. ■


Questions

  1. What type of proof are you providing feedback for (e.g., proof by contradiction, proof using a definition, proof by induction, etc.)?
  2. Do you find the proof presented in a way that is clear or confusing to understand?
  3. What is one thing that you like about this proof and/or that this proof does well?
  4. What is one thing that could be improved in this proof?
  5. Is this proof entirely correct? Please explain your reasoning carefully here.