> I was thinking that it has to do with accepting states in Touring Machine. You should just switch them so the complexity should be the same but I'm not sure. That argument does not always work. You are probably thinking of the proofs that REG and R are closed against complement. Note how the same technique alread breaks down for CFL; it's not that easy for NPDA (or, in fact, for any non-deterministic automaton model). Also, we know that RE ≠ co-RE so the technique does not even work for all deterministic models. This leads me to this answer: the flip-final-state technique works for *membership* in some *deterministic* classes; I'm not sure if *completeness* then works out as well, but my gut feeling is yes. The technique is unlikely to work even for membership in *nondeterministic* classes. As a matter of fact, we do *not* know if NP = co-NP and, as a consequence, we do not know if NPC = co-NPC. And, of course, REC ≠ co-REC. --- Another thing to keep in mind is that the notion of completeness depends on the type of reduction you consider. For instance, above mentionen open question about co-NPC and NPC applies only to Karp reductions; under Cook reductions, co-NPC = NPC (see e.g. [here](http://cs.stackexchange.com/questions/14278/mathsfco-text-np-and-cook-reductions)).