NP и CoNP

[Razor]

Задача из раздела дискретной математики про сложности алгоритмов. Нам надо доказать, что класс NP не замкнут относительно определения.
Допустим у нас есть недетерминированная машина Тьюринга, которая смотрит на принадлежность слова к классу NP (что тоже является недетерменированной МТ), и если слово принадлежит, то говорим что оно не принадлежит нашей МТ, и наоборот.
Где ошибка в рассуждениях? (Если её нет, то получим что NP=coNP)

[Xaositect]

Razor в сообщении #428798 писал(а):

Нам надо доказать, что класс NP не замкнут относительно определения

Относительно дополнения? Где же такие задачки задают? Для этого ведь надо доказать, что $\mathbf{P}\neq \mathbf{NP}$

Запишите свои размышления нормально. В частности, классу NP принадлежат не слова и не машины, а языки или задачи. И машинам слова тоже принадлежать не могут.

[Razor]

Есть язык L, принадлежащий классу NP. N - недетерминированная машина Тьюринга с полиномиальным временем работы, определяющая принадлежность слова w языку L.

На её основе строим новую недетерминированную машину Тьюринга М с полиномиальным временем работы: она прогоняет слово w через N и возвращает 1, если N возвращает 0, и наоборот.

По сути, требуется показать, что множество слов, принимаемых M, не совпадает с дополнением к языку L.

[Xaositect]

А теперь вспоминаем, что недетерминированная машина возвращает 1 если хотя бы одна ветвь вычисления возвращает 1.
То есть если на некотором слове при одном значении недерминированного выбора будет 1, а при другом 0, то слово будет приниматься как машиной N, так и машиной M.

[Razor]

Серднечно благодарю.