Email Print Share

All Images


Research News

Tackling intractable computing problems

theoretical computer science

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


Download the high-resolution PNG version of the image. (584.0 KB)

Use your mouse to right-click (Mac users may need to Ctrl-click) the link above and choose the option that will save the file or target to your computer.

theoretical computer science

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


Download the high-resolution JPG version of the image. (154.9 KB)

Use your mouse to right-click (Mac users may need to Ctrl-click) the link above and choose the option that will save the file or target to your computer.

theoretical computer science

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

Credit: Center for Computational Intractability


Download the high-resolution JPEG version of the image. (141.0 KB)

Use your mouse to right-click (Mac users may need to Ctrl-click) the link above and choose the option that will save the file or target to your computer.