The main theme of this work is to provide a new characterization of the algebraic complexity class VNP. We achieve this via following the two main steps -
- We define a combinatorial variant of the determinant polynomial which we call the colored determinant and show it to be VNP-complete under p-projections for all fields. This adds a new non-monotone VNP-complete polynomial sequence to the already known list of non-monotone VNP-complete polynomial sequences.
- Using the colored determinant polynomial, we show that a new variant of stack branching program, called the conditional stack branching program, characterizes the class VNP.