2018 October 30,

CS 254: Day 21

Carleton College, Joshua R. Davis

A. Problem 7.4 (CFL recognition, related to class last Friday).

Is NP closed under complementation? Nobody knows, but the common suspicion is that NP is not closed under complementation. Explain what is wrong in each of the following "proofs" that NP is closed under complementation. (The proofs are extremely similar, but they make very different mistakes. And ^c denotes complementation.)

B. Let A be an element of NP. Then there exists an NTM N and natural number k such that L(N) = A and the running time of N is O(n^k). Define a TM M that, on input w, runs N on w and outputs the opposite of what N outputs. Then L(M) = L(N^c) = A^c, and the running time of M is O(n^k). So A^c is an element of NP.

C. Let A be an element of NP. Then there exists an NTM N and natural number k such that L(N) = A and the running time of N is O(n^k). Define an NTM M that, on input w, runs N on w and outputs the opposite of what N outputs. Then L(M) = L(N^c) = A^c, and the running time of M is O(n^k). So A^c is an element of NP.

(There was a typographical error in the problems, which was fixed on the morning of Tuesday October 30.)