<p>The complementary version given by Wikipedia is <strong>correct</strong>.</p>

<p>coNP consists of the <em>complements</em> of the problems in NP. In this case, the universe of discourse (i.e., the encoded instances) is the set of (properly encoded) graphs. The Hamiltonian cycle decision problem contains those graphs which are Hamiltonian; its complement is exactly the set of graphs which are not Hamiltonian. </p>

<p>You are correct; the two problems <em>do</em> look almost the same. This is a vital realization concerning coNP (or any co-class in fact). The key difference is that, for some problem classes, being able to efficiently check whether a solution is correct (NP) does <em>not</em> necessarily mean you can also efficiently verify all answers are incorrect (coNP) and vice-versa. </p>

CC BY-SA 4.0
2018-12-31T23:24:30.790Z
So, it seems to me that the Hamiltonian cycle is both in NP and co-NP. Otherwise, what am I missing?
Jérôme Verstrynge
CC BY-SA 4.0
2018-12-31T23:53:25.930Z
@Jérôme Verstrynge Given a graph and a cycle, you can easily check if it is a Hamiltonian cycle (NP). Can you also easily check if *all* cycles are *not* Hamiltonian (i.e., no cycle is Hamiltonian; coNP)? I think not.
dkaeae
CC BY-SA 4.0
2019-01-01T08:44:35.467Z
Well, NP is not only about checking if a cycle is Hamiltonian. It is about finding any that would be Hamiltonian. If you find any, then you also solve the "complementary" version of the problem immediately and if you can't find any, then it means you have exhausted (or eliminated) all possibilities, which is, by definition the "complementary" problem itself. This is why I think NP = co-NP here. Anyway, thanks, you have clarified the concept for me. That was my question.
Jérôme Verstrynge
CC BY-SA 4.0
2019-01-01T11:48:44.277Z
@Jérôme Verstrynge Be careful: NP is *not* a class of search problems! It is the class of decision problems for which poly-bounded advice strings (i.e., NP witnesses) exist such that positive answers may be checked efficiently. NP is about *verifying* answers, not finding them! The search problem of finding an NP witness is only tangential to the matter at hand (and probably the source of your confusion).
dkaeae
CC BY-SA 4.0
2019-01-01T15:30:40.567Z
I get your point. It's just that we don't agree because I think we have different opinion on what constitutes NP. Deciding whether a graph contains a HC or deciding whether a candidate witness is a HC are two different deciding problems. Yet, IMHO they are "very" related to the extent of being inseparable. Finding an HC is often described as a NP problem in many books and articles.
Jérôme Verstrynge
CC BY-SA 4.0
2019-01-01T18:05:50.350Z
@Jérôme Verstrynge This is hardly a matter of "opinion" since there is no dissension concerning the definition of NP (at least not in the proper circles of science). NP contains *decision* problems. Period.
dkaeae
CC BY-SA 4.0
2019-01-02T00:32:07.707Z
_Finding an HC is often described as a NP problem in many books and articles._
This is plainly not true.I do not know which books you are reading, but go on and read a proper complexity book like Papadimitriou, Arora&Barak, Goldreich. (e.g.: http://theory.cs.princeton.edu/complexity/book.pdf Section 2.6.1)
PsySp
CC BY-SA 4.0
2019-01-02T11:54:28.783Z
@dkaenae Ok, I stand corrected on the 'official' definition of NP.
Jérôme Verstrynge
CC BY-SA 4.0
2018-12-31T22:33:02.377Z
2018-12-31T22:40:08.600Z
2018-12-31T22:40:08.600Z
dkaeae
<p>Jérôme, it seems to me that your initial confusion may be due to (unfamiliarity with) the different notions of Turing reduction and Karp reduction (at least, this was the case for me when I incurred into that very same confusion years ago; judging from your question and comments I can perceive my own flawed objections I had at that time).</p>

<p>What you (seem to) suggest in your comment, i.e. to invoke a solver for the <span class="math-container">$\mathbf{NP}$</span> problem and to invert its answer in order to solve the corresponding <span class="math-container">$\mathbf{coNP}$</span> problem, is a Turing reduction from Non-Hamiltonian Graph to Hamiltonian Graph: in order to solve the former problem we just give the same input graph to a subroutine which is able to solve the latter problem, and return YES if and only if the subroutine returned NO. Doing so does not remotely constitute a proof that Non-Hamiltonian Graph and Hamiltonian Graph have the same complexity, nor that <span class="math-container">$\mathbf{coNP} \subseteq \mathbf{NP}$</span>, it is just an instantiation of the fact that <span class="math-container">$\mathbf{coNP} \subseteq \mathbf{P^{NP}}$</span>, i.e. that you can efficiently solve any <span class="math-container">$\mathbf{coNP}$</span> problem using an oracle for any <span class="math-container">$\mathbf{NP}$</span>-complete problem.</p>

<p>Now try to do the same using a Karp reduction instead of a Turing reduction. This is going to be much more uncomfortable: you cannot invert the answer of the subroutine, nor you can perform any manipulation of such answer, you can only return it as it is. The mind-boggling difficulty of proving (or disproving) <span class="math-container">$\mathbf{NP} = \mathbf{coNP}$</span> precisely resides here.</p>

<p>Of course you cannot give the same input graph to the subroutine, as the returned answer would be flat wrong. You have to smartly manipulate the input graph, modifying it in some clever way, and then feed the subroutine with such modified graph, so that the subroutine (which in your suggestion is a solver for Hamiltonian Graph, but in principle can be a solver for any <span class="math-container">$\mathbf{NP}$</span>-complete problem) returns YES if and only if the original input graph is Non-Hamiltonian. See how dramatically clever such manipulation would have to be: it would mean that any Non-Hamiltonian graph given in input is transformed into a Hamiltonian graph (more generally into a YES instance of any <span class="math-container">$\mathbf{NP}$</span>-complete problem, e.g. into a satisfiable CNF formula), and vice-versa! Proving <span class="math-container">$\mathbf{NP} = \mathbf{coNP}$</span> is equivalent to furnish such a fantastic mapping, disproving it is equivalent to proving that no such mapping can exist.</p>

CC BY-SA 4.0
2019-01-03T13:31:46.287Z
Thanks, indeed I was not aware of the difference between Turing and Karp reductions. Now I understand my flaw.
Jérôme Verstrynge
CC BY-SA 4.0
2019-01-03T15:01:47.957Z
You are welcome.
Giorgio Camerani
CC BY-SA 4.0
2019-01-02T19:43:49.287Z
2019-01-02T19:49:04.643Z
2019-01-02T19:49:04.643Z
Giorgio Camerani
<p>It might help to consider a different example. Given a number <span class="math-container">$n$</span>, how would one succinctly prove that it is composite? Well, you can just provide a nontrivial factor.  So COMPOSITES is obviously in NP.  But given a number <span class="math-container">$n'$</span>, how would you prove its not composite (i.e. prime)? That seems a lot harder. You can't just give a non-factor, you want to prove that there are no possible factors among the horde of numbers between 2 and <span class="math-container">$n'-1$</span> (which is exponential in the bit complexity of <span class="math-container">$n$</span>). The space of possible factors is just too big for a proof by exhaustion.</p>

<p>Thus, while COMPOSITES is trivially in NP (problems whose yes instances have simple witnesses), it is a priori far from obvious whether or not it is also in coNP (problems whose no instances have simple witnesses).</p>

<p>Now let's get back to Hamiltonian cycles. if a graph has a Hamiltonian cycle, it's easy to give a witness that the cycle exists: just provide a description of the cycle itself. Thus, Hamiltonian Cycle is in NP. But if a graph does not contain a Hamiltonian cycle, and you want to prove that to someone, there is no good way, as far as anyone knows, to do so.</p>

CC BY-SA 4.0
2019-01-01T17:51:24.477Z
2019-01-01T18:10:41.403Z
2019-01-01T18:10:41.403Z
Yonatan N
<p>I am trying to understand co-NP and its implications properly.</p>
<p>The French Wikipedia <a href="https://fr.wikipedia.org/wiki/Co-NP" rel="nofollow noreferrer">page</a> describing co-NP provides the &quot;complementary&quot; version of the Hamiltonian cycle in co-NP as follows:</p>
<pre><code>Considering a graph G, is it true that it does not have an Hamiltonian cycle?
</code></pre>
<p>Is this correct?</p>
<p>If so, then how is this complementary version a different class of complexity than the original Hamiltonian cycle problem? The decision question is the same. To put it differently, what is the difference between NP and co-NP here?</p>
<p>Otherwise, if this complementary version is false, what would be the correct version (if any exists)?</p>
<p><strong>Update</strong></p>
<ol>
<li><p>To put it simply, returning an opposite answer for one input does not cover for all possible inputs.</p>
</li>
<li><p>In the comments of dkaeae's answer below, I say &quot;<em>NP is not only about checking if a cycle is Hamiltonian. It is about finding any that would be Hamiltonian.</em>&quot; Fact is if a P-machine can decide whether a graph is Hamiltonian or not, it can also deliver an instance of such a cycle in P-time if any exist. This does not harm the formal definition of NP.</p>
</li>
</ol>

<complexity-classes><np>
Hamiltonian cycle vs co-NP
Jérôme Verstrynge
# Hamiltonian cycle vs co-NP

(Asked by: username_0 on 2018-12-31)

I am trying to understand co-NP and its implications properly.
The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows:
Considering a graph G, is it true that it does not have an Hamiltonian cycle?

Is this correct?
If so, then how is this complementary version a different class of complexity than the original Hamiltonian cycle problem? The decision question is the same. To put it differently, what is the difference between NP and co-NP here?
Otherwise, if this complementary version is false, what would be the correct version (if any exists)?
Update

To put it simply, returning an opposite answer for one input does not cover for all possible inputs.

In the comments of dkaeae's answer below, I say "NP is not only about checking if a cycle is Hamiltonian. It is about finding any that would be Hamiltonian." Fact is if a P-machine can decide whether a graph is Hamiltonian or not, it can also deliver an instance of such a cycle in P-time if any exist. This does not harm the formal definition of NP.

**Tags:** complexity-classes, np

---

## 3 answers

### Answer by username_1 on 2018-12-31. Score: 1 | Accepted answer

The complementary version given by Wikipedia is **correct**.

coNP consists of the *complements* of the problems in NP. In this case, the universe of discourse (i.e., the encoded instances) is the set of (properly encoded) graphs. The Hamiltonian cycle decision problem contains those graphs which are Hamiltonian; its complement is exactly the set of graphs which are not Hamiltonian.

You are correct; the two problems *do* look almost the same. This is a vital realization concerning coNP (or any co-class in fact). The key difference is that, for some problem classes, being able to efficiently check whether a solution is correct (NP) does *not* necessarily mean you can also efficiently verify all answers are incorrect (coNP) and vice-versa.

> **Comments:**
> **username_0**: So, it seems to me that the Hamiltonian cycle is both in NP and co-NP. Otherwise, what am I missing?  
> **username_1**: @Jérôme Verstrynge Given a graph and a cycle, you can easily check if it is a Hamiltonian cycle (NP). Can you also easily check if *all* cycles are *not* Hamiltonian (i.e., no cycle is Hamiltonian; coNP)? I think not.  
> **username_0**: Well, NP is not only about checking if a cycle is Hamiltonian. It is about finding any that would be Hamiltonian. If you find any, then you also solve the "complementary" version of the problem immediately and if you can't find any, then it means you have exhausted (or eliminated) all possibilities, which is, by definition the "complementary" problem itself. This is why I think NP = co-NP here. Anyway, thanks, you have clarified the concept for me. That was my question.  
> **username_1**: @Jérôme Verstrynge Be careful: NP is *not* a class of search problems! It is the class of decision problems for which poly-bounded advice strings (i.e., NP witnesses) exist such that positive answers may be checked efficiently. NP is about *verifying* answers, not finding them! The search problem of finding an NP witness is only tangential to the matter at hand (and probably the source of your confusion).  
> **username_0**: I get your point. It's just that we don't agree because I think we have different opinion on what constitutes NP. Deciding whether a graph contains a HC or deciding whether a candidate witness is a HC are two different deciding problems. Yet, IMHO they are "very" related to the extent of being inseparable. Finding an HC is often described as a NP problem in many books and articles.  
> **username_1**: @Jérôme Verstrynge This is hardly a matter of "opinion" since there is no dissension concerning the definition of NP (at least not in the proper circles of science). NP contains *decision* problems. Period.  
> **username_2**: _Finding an HC is often described as a NP problem in many books and articles._ This is plainly not true.I do not know which books you are reading, but go on and read a proper complexity book like Papadimitriou, Arora&Barak, Goldreich. (e.g.: http://theory.cs.princeton.edu/complexity/book.pdf Section 2.6.1)  
> **username_0**: @dkaenae Ok, I stand corrected on the 'official' definition of NP.  

---

### Answer by username_3 on 2019-01-02. Score: 1

Jérôme, it seems to me that your initial confusion may be due to (unfamiliarity with) the different notions of Turing reduction and Karp reduction (at least, this was the case for me when I incurred into that very same confusion years ago; judging from your question and comments I can perceive my own flawed objections I had at that time).

What you (seem to) suggest in your comment, i.e. to invoke a solver for the $\mathbf{NP}$ problem and to invert its answer in order to solve the corresponding $\mathbf{coNP}$ problem, is a Turing reduction from Non-Hamiltonian Graph to Hamiltonian Graph: in order to solve the former problem we just give the same input graph to a subroutine which is able to solve the latter problem, and return YES if and only if the subroutine returned NO. Doing so does not remotely constitute a proof that Non-Hamiltonian Graph and Hamiltonian Graph have the same complexity, nor that $\mathbf{coNP} \subseteq \mathbf{NP}$, it is just an instantiation of the fact that $\mathbf{coNP} \subseteq \mathbf{P^{NP}}$, i.e. that you can efficiently solve any $\mathbf{coNP}$ problem using an oracle for any $\mathbf{NP}$-complete problem.

Now try to do the same using a Karp reduction instead of a Turing reduction. This is going to be much more uncomfortable: you cannot invert the answer of the subroutine, nor you can perform any manipulation of such answer, you can only return it as it is. The mind-boggling difficulty of proving (or disproving) $\mathbf{NP} = \mathbf{coNP}$ precisely resides here.

Of course you cannot give the same input graph to the subroutine, as the returned answer would be flat wrong. You have to smartly manipulate the input graph, modifying it in some clever way, and then feed the subroutine with such modified graph, so that the subroutine (which in your suggestion is a solver for Hamiltonian Graph, but in principle can be a solver for any $\mathbf{NP}$-complete problem) returns YES if and only if the original input graph is Non-Hamiltonian. See how dramatically clever such manipulation would have to be: it would mean that any Non-Hamiltonian graph given in input is transformed into a Hamiltonian graph (more generally into a YES instance of any $\mathbf{NP}$-complete problem, e.g. into a satisfiable CNF formula), and vice-versa! Proving $\mathbf{NP} = \mathbf{coNP}$ is equivalent to furnish such a fantastic mapping, disproving it is equivalent to proving that no such mapping can exist.

> **Comments:**
> **username_0**: Thanks, indeed I was not aware of the difference between Turing and Karp reductions. Now I understand my flaw.  
> **username_3**: You are welcome.  

---

### Answer by username_4 on 2019-01-01. Score: 1

It might help to consider a different example. Given a number $n$, how would one succinctly prove that it is composite? Well, you can just provide a nontrivial factor. So COMPOSITES is obviously in NP. But given a number $n'$, how would you prove its not composite (i.e. prime)? That seems a lot harder. You can't just give a non-factor, you want to prove that there are no possible factors among the horde of numbers between 2 and $n'-1$ (which is exponential in the bit complexity of $n$). The space of possible factors is just too big for a proof by exhaustion.

Thus, while COMPOSITES is trivially in NP (problems whose yes instances have simple witnesses), it is a priori far from obvious whether or not it is also in coNP (problems whose no instances have simple witnesses).

Now let's get back to Hamiltonian cycles. if a graph has a Hamiltonian cycle, it's easy to give a witness that the cycle exists: just provide a description of the cycle itself. Thus, Hamiltonian Cycle is in NP. But if a graph does not contain a Hamiltonian cycle, and you want to prove that to someone, there is no good way, as far as anyone knows, to do so.


---

