5 ms·
Computer Scientists Prove That Certain Problems Are Truly Hard
- tylerhou 5y agoTL;DR: they reduced Hamiltonian Path to a polynomial-factoring-like problem, proving the latter is NP-Hard.
- sylware 5y agoIsn't this the type of problem a "quantum" computer with enough qbits could solve extremely quickly?
- LeegleechN 5y 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.
- tromp 5y agoThere is no link to an actual article, but I found a recent paper "Improved Low-Depth Set-Multilinear Circuit Lower Bounds" by Kush and Saraf [1] that includes this reference [LST22] Nutan Limaye, Srikanth Srinivasan, and Sébastien Tavenas. Set-multilinear and noncommutative formula lower bounds for iterated matrix multiplication. To appear in STOC that appears to be the subject of this quanta article, and the new paper claims to improve upon their work. From what I gather, these papers construct some polynomial f of degree n in VNP defined over poly(n) many variables, such that any product-depth ∆ set-multilinear formula computing f has size at least a certain exponential in ∆. [1] Improved Low-Depth Set-Multilinear Circuit Lower Bounds