is co-NP-hard contained in EXPTIME-hard or vice-versa?

  • 1
    $\begingroup$ What is EXPTIME-hard? It's always good to include the definition of possibly obscure terms so that your question is self-contained. $\endgroup$ – Kyle Jones Jun 10 '20 at 17:47

It is known that co-NP $\subseteq$ PSPACE $\subseteq$ EXPTIME, so every EXPTIME-hard problem, must also be a co-NP-hard problem (as there is a polynomial time reduction from every $L\in$ EXPTIME to it, and therefore also from every $L\in$ co-NP)

Therefore EXPTIME-hard $\subseteq$ co-NP-hard.

Note that this argument does not hold for co-NP-complete and EXPTIME-complete. This is still an open problem (i believe).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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