Understanding, Coping with, and Benefiting from Intractability
Project funded by the NSF expeditions program.
P is the class of problems for which solutions can be found efficiently (in time that is polynomial in the length of problem description). NP is the class of problems for which solutions can be checked in polynomial time. NP contains P. Most experts believe that the two classes are different, but nobody has found a proof of this.
The term Computational Intractability refers to the phenomenon that many problems seem inherently impossible to solve on current computational models. This phenomenon permeates science, mathematics, and engineering, and it limits our ability to understand nature or to design systems. The Center for Computational Intractability, funded by an NSF/CISE Expeditions Grant, is a joint venture of Princeton University, Institute for Advanced Study, Rutgers University, and New York University. It seeks to bridge fundamental gaps in our understanding about the power and limits of efficient algorithms, which has the potential to revolutionize our understanding of algorithmic processes in a host of disciplines, and cast new light on fields such as quantum computing, secure cryptography, and pseudorandomness. Activities at the center include summer schools, workshops, and seminars. We also seek to promote understanding of computational intractability at all levels (high-school, undergraduate, graduate, and postdoctoral).