Hacker News Reader

If the discrete logarithm problem is NP-hard, then I will eat my hat. The discrete logarithm problem can be solved by Shor's algorithm on a quantum computer, placing it in the complexity class BQP. Anyone who claims that BQP contains an NP-hard problem is selling something - I would bet at a trillion-to-one odds against such a claim (if there were any hope of definitively settling the problem).

Not sure it's misleading, he did write the word "technically", and anyone who knows what NP-complete is knows that NP-hard does not necessarily mean NP-complete. I am a cryptographer and the article is fine.

Also, do you have a citation for "We do know with absolute certainty that the decision problem for DLC is NP-Hard"

DLC is in NP and co-NP. Very unlikely to be NP-hard. It is usually listed as one of the candidates for problems that are NP-intermediate, ie, problems in-between P and NP-hard (should they be different).

See e.g. https://cs.stackexchange.com/a/2765

> While it is true that their presence in NP-Hard does not require their pressence in NP (and thus are not proved NP Complete)

You're confused here. The two conditions for a problem being NP-complete are (1) it being NP-hard and (2) it being in NP.

You suggest (2) is the issue, but usually it's harder to prove (1) rather than (2). In the context of factorization problems, the factors are simply the certificate that satisfy condition (2).