News for hackers. Stuff that matters.
Re:The 2-Maxsat Problem Can Be Solved in Polynomial Time by Kranar on Thursday April 27, 2023 @02:24PM (#35732477)
I think you're mixing up quite a lot of things here. For one, apart from the impreciseness of your statement of the decision problem, it wouldn't be a decision problem for ECDLP but rather for the more general discrete logarithm problem (DLP). ECDLP is assumed to be in a higher complexity class than DLP.

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.

Re:The 2-Maxsat Problem Can Be Solved in Polynomial Time by tgflynn on Thursday April 27, 2023 @02:58PM (#35732955)
A decision problem as used to define the classes NP and P is of the form: does there exist an x such that F(x) = 1, where F is a P-time computable function.

If you can solve that problem in P-time then you can also solve the functional version (find an x for which F(x) = 1) in P-time simply by setting each bit to a value for which the decision problem is satisfiable, one by one.

Re:The 2-Maxsat Problem Can Be Solved in Polynomial Time by tromp on Thursday April 27, 2023 @03:00PM (#35732991)
> 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.

[1] https://en.wikipedia.org/wiki/Discrete_logarithm