COMS 482: unofficial class blog

Recall that we write “x is in P if there exists a polynomial time algorithm a(*) such that s is in x if and only a(s) returns yes.” Define x’ = { s | s not in x}. Is x’ in P? Yes, because we can define a’(*) as follows:

if a(s) returns “yes” then return “no” otherwise return “yes”

Let y be in NP. What about y’? Let y’ = {s | s not in y}. To say “y is in NP” means that there exists a polynomial time certifier b(*,*): s is in y if and only if there exists t such that b(s, t) returns “yes,” in polynomial bounded size. So, let’s look at y’:

s in y’
<=> s not in y
<=> ! there exists t such that b(s,t) returns “yes”
<=> for all t, b(s, t) returns “no”

Co-NP = {y’ | y is in NP}. Does NP = Co-NP? We don’t know. If we assume P=NP, though, it follows that P=Co-NP as well. Generally the consensus is that NP does not equal Co-NP. Here is a diagram that might help explain P, NP, Co-NP, and PSPACE:

P-SPACE is defined as {x | x has an algorithm using at most polynomial space}. P is a subset of PSPACE, because you cannot use more than polynomial space in only polynomial time. To say x is in PSPACE implies that x’ is in PSPACE using the same inversion algorithm as above. You can also create the following chain:

x in Co-NP => x’ in NP => x’ in SPACE => x in PSPACE