In his seminal paper, Valiant defined algebraic analogs for the complexity classes P and NP, which are called today VP and VNP, and showed that the permanent is complete for VNP. In this talk we study a more restricted algebraic world, a world in which the variables do not commute and associate. We show that, although restricted, this world exhibits some interesting properties: the permanent is complete even in the non-associative non-commutative version of VNP. We are also able to prove lower bounds for circuits in such a restricted world, and thus able to separate VP from VNP in a non-associative world.

Joint work with P. Hrubes and A. Wigderson.