0
$\begingroup$

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?

1 Answers 1

2

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.

  • 0
    Okay, new answer then.2012-08-05