0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, that clarifies it completely. $\endgroup$
    – user154939
    Commented Jun 17, 2023 at 14:41

Your Answer

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