1
$\begingroup$

If we assume that NP is not equal to co-NP, how do we show that EXPTIME \ NP is not a subset of NP-Hard?

$\endgroup$
1
$\begingroup$

Hint: note co-NP $\subseteq$ EXPTIME, and co-NP-complete $\cap$ NP = $\emptyset$ since NP $\neq$ co-NP, it remains to prove co-NP-complete $\nsubseteq$ NP-hard.

Further hint: if co-NP-complete $\subseteq$ NP-hard, try to show for each language $L\in$ NP, you can build a NTM deciding $\bar L$, thus NP $\subseteq$ co-NP, a contradiction.

$\endgroup$

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.