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

  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).

задан 9 Май '18 0:54

По поводу пункта 1: ошибка бросается в глаза, так как рассмотрен один конкретный алгоритм решения SAT, имеющий экспоненциальную сложность. Но отсюда никак не следует, что нет принципиально лучшего алгоритма.

Про co-NP когда-то что-то на форуме спрашивали -- можете поискать. Только там в определении знак дополнения исчез.

(9 Май '18 1:36) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×819
×396
×211
×130
×55

задан
9 Май '18 0:54

показан
491 раз

обновлен
9 Май '18 1:36

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru