1. Мы видели, что задача 3-SAT относится к NP-полным. Напротив, оказывается, что задача 2-SAT — вариант, в котором в каждом предложении разрешены лишь две переменные, — решается за полиномиальное время. Объясните, почему.

2. Вспомним, что EXP — это класс задач, решаемых за экспоненциальное время. Можно определить также класс NEXP: класс задач, для которых ответ «да» может быть проверен за экспоненциальное время. Иными словами, NEXP для EXP то же самое, что NP для P. Далее, мы не знаем, верно ли P = NP, и не знаем также, верно ли EXP = NEXP. Но мы точно знаем, что если P = NP, то EXP = NEXP. Почему?

3. Покажите, что P не равняется SPACE(n) (множеству задач, решаемых с использованием линейного объема памяти). Подсказка: вам не нужно доказывать, что P не входит в SPACE(n) или что SPACE(n) не входит в P, нужно доказать только, что верно то или другое.

4. Покажите, что если P = NP, то существует алгоритм полиномиального времени, позволяющий не только определить, является ли булева формула выполнимой, но и найти входную строку, для которой она выполняется, если таковая существует.

5. [Повышенной сложности.] Приведите в явном виде алгоритм, позволяющий найти входную строку (если таковая существует), для которой выполняется формула, и выполняемый за полиномиальное время, при условии, что P = NP. (Если формула невыполнима, ваш алгоритм может вести себя произвольным образом.) Иными словами, приведите алгоритм для задачи 4, который можно реализовать и выполнить прямо сейчас, без привлечения какой бы то ни было подпрограммы, которая, как вы полагаете, существует, но которую вы не в состоянии описать.