One goal of the intractability research is develop machine learning algorithms with provable guarantees about the quality of the solutions or the time it will take to run the algorithm.

Credit: Center for Computational Intractability

Is finding solutions no harder than checking them? Can the ability to find good solutions ("creativity") become as routine as the ability to appreciate good solutions? 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. If P=NP then creativity (in almost every conceivable discipline) can be automated. Cryptography becomes impossible. Trying to understand the relationship of P and NP seems fundamental to understanding computation. This question relates to the notion of computation itself, not merely about a specific model.

Credit: Sanjeev Arora, Princeton University

The biennial Women in Theory workshop brings together current and future leading female researchers.

Credit: Center for Computational Intractability