В первой половине XX века математики много спорили о приемлемости неконструктивных доказательств существования. Тогда большинство сошлись на том, что они приемлемы. В середине XX века экономисты доказали множество теорем о существовании экономических равновесий в тех или иных моделях. Как правило, эти теоремы доказываются именно неконструктивно, при помощи топологических теорем о неподвижных точках. Но если пытаться что-то предсказать при помощи этих моделей, то вопрос о конструктивности встаёт вновь. Ведь мало обосновать существование равновесия, надо суметь его найти, причём за разумное время.

С точки зрения сложности вычислений подобные задачи образуют класс TFNP (total functional NP). Более точно, задача состоит в том, чтобы по данному x найти y, такой что выполнено V(x,y). При этом V вычисляется за полиномиальное время, и хотя бы один y существует для любого x (это свойство называется тотальностью). По всей видимости, в этом классе нет полных задач: непонятно, как в общем случае проверять тотальность. Основной метод анализа состоит в том, чтобы выделять те или иные математические принципы, из которых следует тотальность, и рассматривать классы задач, основанных на одном принципе. Наиболее известны классы PLS, PPA, PPAD и PPP, введённые Христосом Пападимитриу. Оказалось, что задачи, связанные с экономическими равновесиями, попадают в класс PPAD, и многие из них полны в нём. В курсе будет дан обзор современного состояния этой области: на первых двух лекциях излагается классическая теория, на вторых двух - достижения последних лет.