4
$\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!

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
6
$\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.

Improve this answer
$\endgroup$
3
  • $\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$
    – Fraïssé
    Dec 2, 2015 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, 2015 at 5:14
  • $\begingroup$ I think that it is worth noticing that, if $P = NP$, which is unlikely as you said, then the NP-hard problems, which would be solvable in polynomial time, are exactly the NP-complete problems. And the other NP-hard problems can not necessarily be reduced to a NP-complete problem and hence would still not be solvable in polynomial time. $\endgroup$
    – Ubuntix
    Aug 19, 2020 at 10:34
5
$\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 ..)

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Upvoted for the intuition provided, despite the unfinished sentence at the end. $\endgroup$
    – Fizz
    Apr 2, 2021 at 14:20
  • 1
    $\begingroup$ very helpful indeed $\endgroup$
    – Sam
    Jan 27 at 4:36
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$.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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