1
$\begingroup$

I'm looking for an information about closure of complexity complete classes.

Is it true that any language, if the language is X-complete, then its complement is X-complete? Why?

I was thinking that it has to do with accepting states in Turing Machine. You should just switch them so the complexity should be the same but I'm not sure.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ In the last but one paragraph, you should probably write "nondeterministic time classes". It works just fine for nondeterministic space classes, because of the Immerman-Szelepcsényi theorem. $\endgroup$
    – Emil Jeřábek
    Commented Apr 5, 2016 at 12:17
  • $\begingroup$ Do you know something about completeness? Can the OP's question be answered positively for space classes? $\endgroup$
    – Raphael
    Commented Apr 5, 2016 at 12:18
  • $\begingroup$ Well, usual notions of reduction (many-one, Turing) have the property that if $A$ reduces to $B$, then the complement of $A$ reduces to the complement of $B$ by the same reduction. It follows immediately that if a language $A$ is complete under such reductions for a class closed under complement (such as typical deterministic classes, or $\mathrm{NSPACE}(f(n))$ for $f(n)\ge\log n$), then so is the complement of $A$. $\endgroup$
    – Emil Jeřábek
    Commented Apr 5, 2016 at 16:15
  • $\begingroup$ @EmilJeřábek Great! I think you should post an answer, pointing out how my answer only applies to time classes. $\endgroup$
    – Raphael
    Commented Apr 5, 2016 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.