Understanding the Mulmuley-Sohoni Approach to P vs. NP.

Kenneth W. Regan

Bulletin of the European Association for Theoretical Computer Science · 2002 · 33 citations · 10 references

Concepts

Abstract

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.

References

10