Valiant's conjecture that VBP differs from VNP
Statement
Let be the class of polynomial families computable by polynomial-size algebraic branching programs, and let be Valiant's class of polynomially verifiable families. The inclusions satisfy . Valiant's conjecture. We have
This is a central separation question in algebraic complexity theory; the source gives no resolution.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.