The definitions come from Turing Reduction of Wikipedia
In computability theory, a Turing reduction (also known as a Cook reduction) from a problem A to a problem B, is a reduction which solves A, assuming the solution to B is already known (Rogers 1967, Soare 1987). It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B. More formally, a Turing reduction is a function computable by an oracle machine with an oracle for B. Turing reductions can be applied to both decision problems and function problems.
which can be simplified as $A$ is reduced to $B$;
- If $A \leq B$ then, if you were given a subroutine for $B$ you could solve $A$.
- This can be also mean that $A$ is no harder than $B$.
I am wondering if this is the right direction. Assume we reduce the problem of breaking a cipher $P$ to some problem $X$, $P \leq_m^p X $, as suggested by the book (if I understand correctly). Then if we have a polynomial-time algorithm for $X$, we also have a polynomial algorithm for $P$. But this does not guarantee that if no polynomial algorithm for $X$ exists, there should be no polynomial-time algorithm for breaking $P$. In fact, there could still be a polynomial-time algorithm breaking $P$ in some way unrelated to problem $X$.
So we have $P \leq X$, which means we use $X$ as a subroutine and $P$ is not harder than $X$.
Yes, the reduction doesn't say about a polynomial-time algorithm exists or not. If one can prove that there is no polynomial-time algorithm for $X$ than this doesn't mean that there is no for $P$. Because the reduction is just a useful upper bound.
If there is a polynomial-time algorithm for $P$ this can be used to solve $X$ if one can show that $X \leq P$. Otherwise, as stated in the second bullet, the reduction provides only the upper bound.
So shouldn't the reduction be the other way around $X \leq_m^p P$. That is, if we can break $P$ in polynomial time, we can also solve $X$ in polynomial time?
Not exactly, the reduction gives the upper bound. To use a polynomial-time algorithm for $P$ to solve $X$ one needs to show that $X \leq P$.
This way, if $X$ is hard (not polynomial-time solvable), then by contraposition $P$ must also be hard, thus $P$ is at least as hard as X?
What am I missing here?
Assuming that one showed a reduction of $X \leq P$, then the information we have $X$ is no harder than $P$ with $P$ is solvable in polynomial-time. If you show that $X$ is hard ( assuming NP-hard here) then one must look at either the reduction or the hardness of solving $P$ again.