I'm studing C. Petit's work "Faster algorithms for isogeny problems using torsion point images" ([link](https://eprint.iacr.org/2017/571.pdf)) and he talks about meet-in-the-middle approach/strategy for solve some isogenies problems.


Well, what does Petit mean with meet-in-the-middle approach/strategy?


I've read that it's an approach that allows you to reduce the complexity of a problem with the aim of using brute force to solve it, but what does it mean in mathematical language?


Any help will be greatly appreciated.



What is meant by a meet-in-the-middle approach?
The "meet in the middle approach", also known as "bidirectional search", is a method to find shortest paths in graphs. It was proposed by Pohl [1] and first used by Galbraith [2] to construct isogenies between elliptic curves $E$ and $E'$. One builds two trees of isogenies from both sides of $E$ and $E'$, and finds a collision between the two trees to obtain the shortest path from $E$ to $E'$.


[1] [Bi-directional and heuristic search in path problems](https://www.semanticscholar.org/paper/Bi-directional-and-heuristic-search-in-path-Pohl/e609ab97186834bd97d3fbc0c97a19744d752c23), I Pohl (1969).  

[2] [Constructing isogenies between elliptic curves over finite fields](https://www.math.auckland.ac.nz/~sgal018/iso.pdf), S.D. Galbraith (2011).


