Аннотация:
Во многих вычислительных задачах решение всегда существует из-за какой-нибудь математической теоремы наподобие принципа Дирихле, леммы о рукопожатиях или теоремы о неподвижной точке. Более того, корректность решения может быть легко проверена. Но это не спасает от экспоненциального перебора при поиске решения. Стандартный подход в теории сложности - поиск задач, к которым сводятся все остальные - не работает для класса всех тотальных задач. Приходится выделять подклассы, основанные на том или ином принципе, и искать полные задачи внутри них. В докладе будет рассказано про класс PPAD и его связь с задачами математической экономики.
|
