Computer Scientists Prove That Certain Problems Are Truly Hard(quantamagazine.org)

32 pointsby fortran77há 4 anos4 comments

Computer Scientists Prove That Certain Problems Are Truly Hard

https://www.quantamagazine.org/computer-scientists-prove-certain-problems-are-truly-hard-20220511/

2 comments

tromphá 4 anos

There 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

tylerhouhá 4 anos

TL;DR: they reduced Hamiltonian Path to a polynomial-factoring-like problem, proving the latter is NP-Hard.

sylwarehá 4 anos

Isn't this the type of problem a "quantum" computer with enough qbits could solve extremely quickly?

LeegleechNhá 4 anos

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.