математическая-логика - Курс вычислимость и сложность

Здравствуйте! Прошу помочь в решении задач (хотя бы некоторых). Заранее большое спасибо всем, кто хоть немного поможет!!!

1. Рассмотрим следующее доказательство того, что P 6= NP : Рассмотрим следующий разрешающий алгоритм для SAT . На входе A(p1; ... ; pn) перебираем все возможные оценки пропозициональных переменных p1; ... ; pn, если при любой такой оценке формула истинна, то принимаем эту формулу, иначе — отвергаем. Поскольку существует 2^n оценок n пропозициональных переменных, алгоритм требует экспоненциального времени для своего выполнения. Следовательно, проблема SAT имеет экспоненциальную сложность по времени. Получаем, что SAT не принадлежит P . Поскольку SAT принадлежит NP , мы можем заключить, что P не равно NP . В чем состоит ошибка?

2. Рассмотрим сложностной класс coNP = {L | L принадлежит NP}. Докажите, что если NP ⊂ coNP , то NP = coNP .

3. Все слова языка L принимаются машиной Тьюринга M за полиномиальное время, и никакие другие слова машиной M не принимаются (но, возможно, и не отвергаются). Верно ли, что L лежит в P ?

4. Рассмотрим множество T = {n | n — десятичная записть числа 3^k для некоторого k принадлеж. N}. Докажите, что T принадлежит P .

5. Рассмотрим язык POLYTEN = {p(x) | p(x) — многочлен 10-й степени с целым корнем}. Докажите, что POLYTEN принадлежит NP .

6. Рассмотрим следующую задачу. SUDOKU: Дана таблица размера n^2 × n^2, в которой каждая клетка либо пуста, либо содержит некоторое число из множества {1; ... ; n^2}. Таблица разбита на n^2 малых квадратов размера n×n. Можно ли заполнить пустые клетки числами из множества {1;...; n^2} таким образом, чтобы в каждой строке, в каждом столбце и в каждом малом квадрате n × n каждое число из {1;...; n^2} встречалось бы ровно один раз? Докажите, что SUDOKU <=(p m) SAT (SUDOKU сводится за полином к SAT).