Could there theoretically exist a problem $A$ which is in $co$-$NP$, but its complement $A^{C}$ is $EXPTIME$-complete?

I was reading a bit about $$NP$$-problems and how it is widely assumed that $$NP\neq co$$-$$NP$$. This also implies that the complement of $$NP$$-complete problems are not in $$NP$$.

What is known is that the complement of a $$co$$-$$NP$$-complete problem is $$NP$$-complete and it could be that either $$NP=co$$-$$NP$$ or $$NP\neq co$$-$$NP$$.

I wonder though if a complement of a $$co$$-$$NP$$-problem (not necessarily $$co$$-$$NP$$-complete) $$A^{C}$$ can be $$EXPTIME$$-complete? Of course then $$P\neq NP$$ since if $$P=NP$$ we would have $$NP=co$$-$$NP=P\neq EXPTIME$$-complete.

Additionally (sorry if that counts as a second question), I was wondering if - in that case - any algorithm for a $$co$$-$$NP$$-problem $$A$$ with $$A\notin P$$ (and $$A$$ is not complete for $$co$$-$$NP$$) would theoretically have to be superpolynomial in the input size given that $$P\neq NP$$ or whether it is still possible that

• there is a polynomial time algorithm for $$A\in co$$-$$NP$$
• $$A^{C}\in EXPTIME$$-complete

In that case $$A\notin P$$ since $$P$$ is closed under complement (which means that problems in $$P$$ can be defined as those problems for which their complements are also in $$P$$, as far as I understand).

With regards to the first question: "I wonder though if a complement of a $$co$$-$$NP$$ problem (not necessarily $$co$$-$$NP$$-complete) $$A^C$$ can be $$EXPTIME$$-complete?

The complement of a $$co$$-$$NP$$ language is, by definition, a $$NP$$ language. Hence, you are asking if there can be a $$NP$$ language which is $$EXPTIME$$-complete. This is the same as asking whether $$NP=EXPTIME$$, which is not known.

To see that your question is equivalent to ask $$NP=EXPTIME$$, notice that, if $$NP=EXPTIME$$, any $$NP$$-complete language would be $$EXPTIME$$-complete. On the other hand, if we had a $$NP$$ language in $$EXPTIME$$-complete, we have that all $$EXPTIME$$ languages could be reduced to it, and hence, $$NP=EXPTIME$$.

With regards to the second question: In the first part you say "any algorithm for a $$co$$-$$NP$$ problem $$A$$ with $$A \not\in P$$ would have to be superpolynomial?" If $$A \not\in P$$, then, by definition, any algorithm to solve $$A$$ will need to be superpolynomial.

In the second part you say "or is it possible that there is a polynomial time algorithm $$A \in$$co-$$NP$$ such that $$A^C \in EXPTIME$$-complete".

If you have a (deterministic) polynomial algorithm that decides $$A$$, you have a (deterministic) polynomial algorithm that decides $$A^C$$ by just negating the answer of the algorithm. In essence, you are asking if you can have an algorithm that decides an $$EXPTIME$$-complete languge in polynomial time, that is, you are asking if $$P = EXPTIME$$-complete, which, as you already know, is not true.

• Thanks, that clarifies it completely.
– user154939
Commented Jun 17, 2023 at 14:41