An introduction to geometric complexity theory (Q737196)

One of the most prominent open questions in theoretical computer science is the ``P vs. NP'' problem. It is listed as one of the Millennium Problems by the Clay Mathematics Institute. Let P denote the class of problems that can be solved in polynomial time (w.r.t. the size of the input) by a deterministic Turing machine; let NP denote the class of problems that can be solved in polynomial time by a nondeterministic Turing machine. NP can also be thought of as the class of problems for which a proposed solution can be checked in polynomial time. The ``P vs. NP'' problem consists of the question whether P = NP or not, i.e., whether every problem whose solution can be checked in polynomial time can also be solved in polynomial time. In this article an algebraic variant of the ``P vs. NP'' problem is considered, namely Valiant's conjecture comparing the complexity of the permanent and determinant polynomials. Methods from differential geometry, algebraic geometry and representation theory are presented relying on Valiant's conjecture. The current state of the art is presented.