Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

consider the following language: $HAM-NO-HAM=\{(G_1,G_2)|G_1, G_2\}$ are undirected graphs, $G_1$ has a Hamilton and $G_2$ doesn't have one$\}$.

i need to decide wheter it's in $P, NP, CONP$ or none of the above.

If I'll show reductions from $HAMcircuit$ and from $NO-HAMcircuit$ I will get that $HAM-NO-HAM$ is both $NPC$ and $coNPC$.

What is the best way for showing a reduction from the $HAMcircuit$ to $HAM-NO-HAM$?

I want somehow to copy it and then I would get the graph which does or doesn't have a $HAMcircuit$ but I need to copy it again so it would fit the other other condition for the second graph.

Any suggestion?

share|cite|improve this question
up vote 2 down vote accepted

In order to reduce from HAM (or noHAM), just take the input graph and pair it with a fixed graph that you already know not to have (respectively, to have) a Hamiltonian circuit.

However, what these reductions prove is just that the problem is (co)NP-hard, not that it is complete. To be complete, is must both be hard and actually be in (co)NP. And those same reductions show that your problem cannot be (co)NP unless NP=coNP, which is unknown but believed to be false.

share|cite|improve this answer
sorry, I messed up the question. please see my edit. – Jozef Aug 5 '12 at 14:17
Okay, new answer then. – Henning Makholm Aug 5 '12 at 14:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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