2
$\begingroup$

I was watch this lecture https://youtu.be/moPtwq_cVH8?t=2895, and at this point he says a lot about reductions, take a problem and reduce to another problem. From what I could understand this is a symmetric relation, if I can reduce A to B, then I can reduce B to A. This seems pretty intuitive to me but I don't have a formal proof, is there any (for beginners would be better) material on this proof?

Still on this lecture, from what I could understand we have problems that are known to be NP-hard, if I have a problem that I don't know what is but I can reduce to NP-hard problem then it must be NP-hard.

Another question, supposing that reduction is symmetric if any NP problem can be reduced to P problem that would prove that P = NP. Or in reverse, if I have a known NP problem and I prove it can't be reduced to a P problem then this would prove that P ≠ NP.

Is my reasoning right? I'm not trying to prove anything just want to make sure that I understand the reduction implications because this seem powerful tool for day reasoning on solving problems in general.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Reduction is not symmetric. Intuitively, if $A$ reduces to $B$, then $B$ is at least as hard as $A$. Just as the usual comparison is not symmetric — for example $3 > 2$ but $2 \not> 3$ — reduction, which is a (partial) order of hardness, isn't symmetric.

For example, SAT reduces to the halting problem, but the halting problem doesn't reduce to SAT.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Partial order of hardness, thank you so much for that, now it's clear $\endgroup$
    – geckos
    Commented Apr 22, 2021 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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