recently there has been major progress into the VP=?VNP problem for algebraic circuits originated by Valiant, inspiring some optimistic outlook on its eventual or imminent resolution.[1]

what is an outline/ overview of an intuition that VP=?VNP is connected or not (closely?) connected to the P=?NP problem?

am looking for "not complex" or "straightforward" sketches or constructions, not necessarily "rigorous".

[1] Recent Progress on Arithmetic Circuit Lower Bounds / Ramprasad Saptharishi, Bulletin of EATCS

The field of arithmetic circuit complexity has lately seen a flurry of results. Several of these results are centered homogeneous depth four circuits, and come tantalizingly close to separating the algebraic analogue of P from the algebraic analogue of NP.

[2] Does $VP \neq VNP$ imply $P \neq NP$?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.