Search code examples
complexity-theory

Determine universe of complementary

i'm thinking about problems in P complexity, and i have a question:

If a problem "A" is a problem in P, his complementary have to be a problem in P? Why?

Solution

  • Because every algorithm to decide A can be trivially turned into one deciding not(A) simply by negating the answer. That doesn't change its complexity.

    As you can see from this argument, that's not a special property of the class P. The same argument applies to all deterministic complexity classes, hence they are all closed under complement: DTIME(f(n)) = co-DTIME(f(n)) for all f.