Тим Рафгарден начинает с обманчиво простого вопроса: есть ли у компьютеров что-то, чего они не могут сделать? Чтобы ответить, он возвращается к 1936 году — задолго до появления реальных машин Алан Тьюринг, решая obscure математическую задачу, заложил основы computer science. Его статья представила теоретическую машину и доказала сокрушительное: существуют проблемы, которые не решит ни один алгоритм, сколько бы времени или мощности вы ему ни дали. Проблема остановки (halting problem) — будет ли программа когда-либо выполнена — навсегда находится за пределами возможностей любого компьютера.
Отсюда Рафгарден переходит к более тонкому вопросу. Среди решаемых задач — какие из них можно решить быстро? Он знакомит с алгоритмическими сокращениями — хитрыми приёмами, которые позволяют программе не перебирать все варианты. Карты на телефоне строятся на алгоритме Дейкстры, находящем кратчайший маршрут без проверки каждого мыслимого пути. Метод умножения Карацубы бьёт школьный способ. Эти сокращения кажутся почти волшебством и порождают надежду: возможно, такие приёмы существуют для любой задачи.
Эта надежда разбивается о задачу коммивояжёра (Traveling Salesman Problem). Хотя она выглядит почти так же, как поиск кратчайшего пути, TSP сопротивляется любым попыткам найти быстрый алгоритм. Рафгарден объясняет, как эта головоломка привела к теории NP-полноты — одному из самых неожиданных открытий computer science. Тысячи, казалось бы, не связанных проблем (расписания, головоломки, оптимизация сетей) оказываются замаскированными версиями одного и того же вызова. Если кто-то найдёт быстрый алгоритм для одной — решёнными станут все. Если хоть одна по-настоящему трудна — все трудны.
Это подводит к P versus NP — важнейшему открытому вопросу computer science и одной из великих нерешенных задач математики. Рафгарден прослеживает её историю через имена Гильберта, Гёделя и фон Неймана, показывая, как две отдельные исследовательские традиции — одна об успехах алгоритмов, другая об их ограничениях — сошлись в едином вопросе. Курс завершается обсуждением того, что ответ может значить для криптографии, искусственного интеллекта, квантовых вычислений и нашего понимания вычислений как таковых. Никакого предварительного опыта в computer science или математике не требуется.