1
$\begingroup$

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!

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So NP hard and coNP hard only implies that there is no efficient "general" algorithm, but does not imply that a solution cannot be found (in certain special cases, or using special methods)? $\endgroup$ – Carlos - the Mongoose - Danger Dec 2 '15 at 5:10
  • 2
    $\begingroup$ If P$\neq$NP (as is widely believed) then no NP-hard problem has a polynomial time algorithm. However, most problems encountered in practice can be solved given enough time (perhaps an unrealistic amount of time, say a few million years, depending on the instance size). Some problems are even harder, and cannot be solved even in principle, for example the halting problem. $\endgroup$ – Yuval Filmus Dec 2 '15 at 5:14
3
$\begingroup$

When wikipedia says the complement, that's literally what it means:

A problem $L$ is in NP if there's a non-deterministic Turing Machine $M$ that, for every word $w \in L$, that accepts $w$ in polynomial time.

A problem $L$ is in co-NP if there's a non-deterministic TM that rejects all words $x \not \in L$ in polynomial time.

The question is, if you have the "guessing" that a non-deterministic TM gives, does it help you find yes solutions fast, or no-solutions fast?

For example, there are a bunch of $coNP$ hard problems asking, for some sets $S, T$, is $S \subseteq T$. If have an element $x \in S, x \not \in T$, then we can verify in polynomial time that the subset relation does not hold.

There is a problem in NP for every problem in coNP, and vice versa. For example, the SAT problem asks "does there exist a boolean assignment which makes this formula evaluate to True?". The complement problem, which is in coNP, asks, "do all boolean assignments make this formula evaluate to False?"

Being coNP hard just means that you can reduce in polynomial time from every other problem in coNP. So if a problem is NP-hard, its complement is coNP hard.

The reason this is interesting is, we don't actually know if $NP = coNP$. The general hypothesis is that it does not. If we assume $NP \neq coNP$, then you can prove that a problem is not NP-complete (or coNP complete) by showing that it is in both $NP$ and $coNP$.

$\endgroup$
1
$\begingroup$

When a problem is NP-complete, it is hard to find out whether the answer is yes or no but if the answer is yes, there are short witnesses that are easy to check (but not easy to find).

For example SAT is NP-complete so if you have a Boolean formula it is hard to say whether it is satisfiable. However, if I tell you that your formula if satisfiable for example by setting $x_1,x_2,x_7,x_8$ to true and the other variables to false, you can check that easily. On the other hand, if I tell you that the formula is not satisfiable, I do not have an easy way of convicing you, short of going through all valuations with you.

Now look at VALIDITY of Boolean formulae, another decision problem. The situation is reversed. If your formula is not valid, I'll convince you easily with a witnessing valuation. While if it is valid, I do not have short witnesses that will convince you. BTW, did I mention that VALIDITY is coNP-complete?

So NP-complete problems have short witnesses for "yes" answers while coNP-complete problems have short witnesses for "no" answers. As they say "the two are the same thing modulo swapping of yes and no so that they are in fact just the opposite".

If we forget about completeness, NP-hard problems may have short easy witnesses for "yes" answers but (unless P=NP) do not have such short easy witnesses for "no" answers. With coNP-hard problems, the "yes" answers do not have short easy witnesses (unless ..)

$\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.