New answers tagged algebraic-complexity
3
The short answer is no these are not known, though they are certainly not out of the question. There are no direct implications known to P vs NP, and we do not even have a conjecture (let alone theorem) that such-and-such a representation is an obstruction iff $VP \neq VNP$.
One can start to get at an implication to ordinary P vs NP by trying to implement ...
Top 50 recent answers are included
Related Tags
algebraic-complexity × 74cc.complexity-theory × 43
arithmetic-circuits × 14
polynomials × 12
ds.algorithms × 11
algebra × 9
circuit-complexity × 8
permanent × 8
determinant × 8
reference-request × 7
lower-bounds × 4
nt.number-theory × 4
big-picture × 3
matrix-product × 3
graph-theory × 2
graph-algorithms × 2
co.combinatorics × 2
complexity-classes × 2
time-complexity × 2
cr.crypto-security × 2
graph-isomorphism × 2
polynomial-time × 2
p-vs-np × 2
gr.group-theory × 2
proof-complexity × 2