Hacker News new | ask | show | jobs
by NoKnowledge 2470 days ago
It's strange that the authors pick integer factorization as the problem to solve on their machine. Although their machine may provide a speedup for optimization problems, these speedups are not relevant for the problem of integer factorization, as shown in https://arxiv.org/abs/1902.01448 (disclaimer: I am a co-author of that paper).

Skimming over the paper it seems their method of translating factorization to the optimization problem consists of simplifying equations without justification that this can be done efficiently. I suspect that their preprocessing step is already NP-hard.

The second and more important issue, is that the overall strategy---of translating a problem with a sub-exponential classical complexity (via the Number Field Sieve) to an optimization problem with exponential runtime---is not expected to succeed, as confirmed by careful measurements in our paper.

1 comments

I agree that the integer factorization is a poor choice. Last statement in the Abstract talks about sampling and optimization which could be the bigger point.

Their pre-processing seems like simply expanding out their cost function that's of the form E= (F - XY)^2. Of course it's a lot of multiplications since X and Y are binary and multi-dimensional. Not sure if it would be NP-hard though.