1
$\begingroup$

I am trying to understand the definition / meaning of reduction.

  1. Is it correct to say that the statement "Problem $A$ reduces to Problem $B$ in $x$-time" is the same as writing $A \leq_{x} B$? For example $\text{SAT} \leq_{polynomial} \text{3-SAT}$.

  2. If we are reducing problem $A$ to $B$ in $x$-time, does it mean that you take an instance in problem $A$, and modify it such that it becomes a valid input for problem $B$, such that the modification is done with $x$ time complexity?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ In the future, please, ask only one question per post. The site format works better that way. $\endgroup$ – D.W.♦ Jan 26 '16 at 5:32
  • $\begingroup$ Our reference question contains comprehensive answers. Basically, you are looking for the definition of $\leq_x$. $\endgroup$ – Raphael♦ Jan 26 '16 at 11:22
0
$\begingroup$

As far as I know, the first point is correct. For the second point you missed the fact that "solve $A$ with the given instance iff solve $B$ with the created instance".

Improve this answer
$\endgroup$

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