1

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$?

vzn
  • 11,014
  • 2
  • 31
  • 64

0 Answers0