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 Answer 1

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 and acknowledge you have read our privacy policy.

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