News for hackers. Stuff that matters.

A comment on Computer Scientists Prove That Certain Problems Are Truly Hard.

Re:Computer Scientists Prove That Certain Problems Are Truly... by tylerhou on Friday May 13, 2022 @12:50AM (#31363456)
TL;DR: they reduced Hamiltonian Path to a polynomial-factoring-like problem, proving the latter is NP-Hard.
[ Parent | on HN ]
Re:Computer Scientists Prove That Certain Problems Are Truly... by sylware on Friday May 13, 2022 @08:37AM (#31366754)
Isn't this the type of problem a "quantum" computer with enough qbits could solve extremely quickly?
[ Parent | on HN ]
Re:Computer Scientists Prove That Certain Problems Are Truly... by LeegleechN on Friday May 13, 2022 @12:04PM (#31369321)
No, 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.
[ Parent | on HN ]