I'm just a little confused about the wordings for reductions and would appreciate some help as I am very new to reductions.

I have a question where I have two sets, A and B, and I have to provide a reduction A $\leq_p$ B and then I have to prove that the reduction is correct.

What does this mean exactly?

For the reduction portion do I have to:

  1. Provide some sort of explanation of B in terms of A?

  2. Provide some sort of explanation of A in terms of B?

  3. Both 1 & 2?

And then I'm assuming to prove the reduction is correct, I need to show A $\implies$ B as well as B $\implies$ A?

(The exact question has A as the set of un-directed graphs with a Hamiltonian path and B is the set of un-directed graphs with a Hamiltonian cycle)

Any clarification would be greatly appreciated!!



Follow the definition of $\leq_p$.

You have to find a function $f$ (define it!), computable in polynomial time (prove this!) such that

$$ \begin{array}{l} \forall x.\ x\in A \implies f(x)\in B \\ \forall x.\ x\notin A \implies f(x)\notin B \end{array} $$ (two more proofs!)

More intuitively, $f$ converts instances of $A$ (i.e. $x$) into instances for $B$ ($f(x)$), and must map $A$ inside $B$, and the complement of $A$ inside the complement of $B$. Very, very roughly, it describes how to solve $A$ exploiting $B$.

Finally, never write nonsense formulas like $A \implies B$ since sets do not imply other sets. Try to be as formal as you can, at least when you have not yet mastered the definition.

| cite | improve this answer | |

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.