News for hackers. Stuff that matters.
Re:The 2-Maxsat Problem Can Be Solved in Polynomial Time by tromp on Thursday April 27, 2023 @12:11PM (#35730278)
Having an efficient algorithm for SAT (or any NP complete problem) immediately gives you an efficient algorithm for ALL problems in NP, including ECDLP.
Re:The 2-Maxsat Problem Can Be Solved in Polynomial Time by Kranar on Thursday April 27, 2023 @01:32PM (#35731654)
It is not known if the decision problem for ECDLP is in NP, in fact it's likely not in NP.

NP-hard does not mean NP, it means a problem that is ATLEAST as hard as NP. NP-hard problems that are in NP are known as NP-Complete.

Finally ECDLP itself is not a decision problem, so even if the decision problem for ECDLP is in NP and P = NP, that does not mean that ECDLP itself has a polynomial time solution.

NP, NP-Complete, NP-Hard etc... only refer to decision problems, not to general purpose computations.

Re:The 2-Maxsat Problem Can Be Solved in Polynomial Time by tromp on Thursday April 27, 2023 @01:46PM (#35731885)
The decision problem for ECDLP

  { (k, P, x) : x is a prefix of the k-bit discrete log of P }
is trivially in NP.
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