Описание:В курсе изучаются способы классификация вычислительных задач по вычислительной сложности. Рассматриваются однородные (машины Тьюринга) и неоднородные (СФЭ) модели вычислений. Изучаются классы задач, построенных на основе вычислений в специальных моделях (недетерминированные вычисления, интерактивные доказательства) с различными ограничениями по сложности (по времени работы алгоритма, по объему используемой памяти, по размеру СФЭ, по объему коммуникационных сообщений). Разбирается понятие эффективного вычисления, приводится и доказывается ряд теорем об иерархии и ускорении, формулируется тезис Эдмондса (полиномиальный тезис Тьюринга). Исследуются различные виды сводимостей между вычислительными задачами, приводятся условные (зависящие от предположения о несовпадении классов P и NP и тп.) нижние оценки сложности вычислений. Вводится понятие релятивизации (вычисления с оракулом) и доказываются теоремы о невозможности разрешения ряда сложностных проблем (в том числе P=NP) с помощью релятивизируемых методов. В курсе рассматриваются основные сложностные классы и доказываются теоремы об их взаимосвязи, в том числе рассматриваются классы полиномиальной иерархии, классы языков, имеющих интерактивные доказательства, экспоненциальные классы сложностей, функциональные классы сложностей, классы, связанные с понятиями параллельной и коммуникационной сложности.