Is reduction symmetric? 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.
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 &gt; 2$ but $2 \not&gt; 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.