ECDLP is assumed to be in a higher complexity class than DLP.
No, it's not. All instances of DLP, including ECDLP, are just asking for an x
such that b^x = a, as Wikpedia will tell you [1]. They only differ in the choice of group, but exponentiation within the group is assumed to be an efficient operation.
With that said, even if the decision problem for ECDLP is in NP, that does not mean that a solution to ECDLP is in P.
It trivially does. You simply start with an empty prefix x and extend it 1 bit at a time by repeatedly asking if (Curve_spec, P, x0) is in the language. If so you continue with x0, if not you continue with x1.
Comments
No, it's not. All instances of DLP, including ECDLP, are just asking for an x such that b^x = a, as Wikpedia will tell you [1]. They only differ in the choice of group, but exponentiation within the group is assumed to be an efficient operation.
It trivially does. You simply start with an empty prefix x and extend it 1 bit at a time by repeatedly asking if (Curve_spec, P, x0) is in the language. If so you continue with x0, if not you continue with x1.
[1] https://en.wikipedia.org/wiki/Discrete_logarithm