3 ms·
TL;DR: they reduced Hamiltonian Path to a polynomial-factoring-like problem, proving the latter is NP-Hard.
by tylerhou 4y ago
TL;DR: they reduced Hamiltonian Path to a polynomial-factoring-like problem, proving the latter is NP-Hard.
- sylware 4y agoIsn't this the type of problem a "quantum" computer with enough qbits could solve extremely quickly?
- LeegleechN 4y agoNo, they can solve integer factoring. This result shows that polynomial factoring is fundamentally different from integer factoring. The latter is believed to not be NP Hard.