Problem Detail: I have a faint notion of what NP hard is (that a problem is legit difficult 3 SAT for example). I have forgotten what coNP hard, and Wikipedia tells me that the complement of coNP hard is NP hard…not really helping there Can someone please clarify for me on an intuitive level what does it mean for a problem to be coNP hard? Further, what does it mean for a problem to be both NP hard and coNP hard? What is a problem that illustrate this concept? Thank you!
Asked By : Beached Whale
Answered By : Yuval Filmus
A language $L$ is NP-hard if for every language $R$ in NP there exists a function $f$ computable in polynomial time such that for all $x$, $x in R$ iff $f(x) in L$. A language $L$ is coNP-hard if for every language $R$ in coNP there exists a function $f$ computable in polynomial time such that for all $x$, $x in R$ iff $f(x) in L$. If a language is both NP-hard and coNP-hard then its exact complexity lies above both NP and coNP. Indeed, it is conjectured that NP$neq$coNP, and this implies that a problem which is both NP-hard and coNP-hard belongs to neither NP nor coNP. Problems which are both NP-hard and coNP-hard do exist. For example, any PSPACE-complete problem is both NP-hard and coNP-hard.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/50209
