2020 February 25,

CS 254: Day 21

Carleton College, Joshua R. Davis

A. Problem 7.4.

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.)

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.