2 ms·
I'm not very familiar with the discrete logarithm problem but it seems to be fairly generally true that many problems which are easy in the continuous case beco
by tgflynn 11y ago
I'm not very familiar with the discrete logarithm problem but it seems to be fairly generally true that many problems which are easy in the continuous case become hard when you try to restrict the solutions to a grid. Even solving the linear equation Ax = b in n dimensions, I believe, is NP hard for x \in {0,1}^n.
- schoen 11y agoI wonder if we could say that this has to do with the integers having measure zero in the reals, so if you want to actually hit them you may need a qualitatively better kind of "aim". (I don't know enough higher math to know if this intuition is meaningful or not.)
- tgflynn 11y agoThere are probably a lot of different ways to look at it. One perspective is that easy problems usually involve convex sets (or minimizing convex functions, which is pretty much the same thing since the solution set is guaranteed to be convex). Discrete sets, such as the vertex set of a hypercube, are trivially non-convex (unless they only contain a single element). You can also think about it geometrically. Imagine you have a plane that passes through a cube. How do you determine if it intersects one of the cube vertices (this is basically equivalent to the subset sum problem) ? Of course it's easy to find a method that will work in 3D, but these methods all end up scaling exponentially with the dimension of the space.
- guilamu 11y agoThanks a lot for your comment, I hope this will help Feldmann.