Understanding the Mulmuley-Sohoni Approach to P vs. NP.
Kenneth W. Regan · Bulletin of the European Association for Theoretical Computer Science · 2002
We explain the essence of K. Mulmuley and M. Sohoni, “Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems” [MS02] for a general complexity-theory audience. We evaluate the power and prospects of the new approach. The emphasis is not on probing the deep mathematics that underlies this work, but rather on helping computational complexity theorists not versed in its background to understand the combinatorics involved.