Глава V. Другие классы труднорешаемых задач

Класс co-NP - дополнений языков из NP. Если P = NP, то класс

co-NP равен обоим, так как класс P замкнут относительно дополнения. Однако более вероятно, что ни одна NP-полная проблема не принадлежит co-NP.

Класс PS содержит проблемы, которые решаются на машинах Тьюринга с полиномиальной емкостной сложностью относительно длины входа. Здесь будет доказано, что при таком ограничении недетерминизм не увеличивает мощности машины Тьюринга. Однако, несмотря на то, что NP Í PS, нет оснований считать эти классы равными. Существует PS-полная проблема, которая предположительно не принадлежит NP.

Рандомизированные алгоритмы, реализуемые машинами Тьюринга, использующими при вычислениях последовательность случайных чисел, и определяемые ими два класса языков - RP и ZPP. Языки класса RP (случайные полиномиальные языки) имеют алгоритм, работающий полиномиальное время, используя генератор случайных чисел. Алгоритм или подтверждает принадлежность входа языку, или отвечает “не знаю”. Кроме того, если вход на самом деле принадлежит языку, повторное применение к нему алгоритма подтвердит принадлежность с вероятностью, близкой к 1. Языки класса ZPP (безошибочные, вероятностные полиномиальные) также используют случайные числа, но алгоритм дает ответ: “да”, если вход принадлежит языку, и “нет” – в противном случае . Ожидаемое время работы алгоритма полиномиально, однако возможно, что выполнение алгоритма потребует больше времени, чем полиномиальное.

Класс co-NP

Класс языков P замкнут относительно дополнения. Пусть LÎ P и L=L(M). Для допускания L^’ изменим M следующим образом: введем новое заключительное состояние q и новые переходы в q из тех состояний, в которых M остановливалась, не допуская, заключительные состояния M сделает недопускающими. Измененная машина Тьюринга допускает язык L^’ и время ее работы совпадает с T(M)+1. Т.е. L^’ Î P, если L Î P.

Hаиболее вероятно, что дополнения NP-полных пробдем не принадлежат NP, поэтому в co-NP нет ни одной NP-полной проблемы.

С другой стороны, дополнения NP-полных проблем принадлежат co-NP, так что не находятся в NP.

Пример. Язык ВЫП принадлежит классу NP, его дополнение НВЫП, содержащее все невыполнимые булевы формулы и слова, не являющиеся кодами допустимых булевых формул, принадлежит co-NP. Вероятно, что НВЫП Ï NP, но доказательство последнего утверждения равносильно проблеме P ¹ NP.

Предполагаемая взаимосвязь между классами на рис.11.1.

Рис.11.1.

NP-полные проблемы и co-NP.

Предположим, что P ¹ NP. Допустим, что NP = co-NP. Тогда проблемы типа НВЫП можно решить за полиномиальное время на недетерминированной машине Тьюринга, но нельзя решить за полиномиальное время на детерминированной машине. Последнее противоречит допущению.

Теорема. NP = co-NPтогда и только тогда, когда существует NP-полная проблема, дополнение которой принадлежит NP.

Доказательство. Необходимость. Если NP = co-NP, то каждая NP-полная проблемаL принадлежала бы как NP, так и co-NP. Но дополнение проблемы из co-NP находится в NP, поэтому дополнение L принадлежит NP.

Достаточность. Пусть R - NP-полная проблема, дополнение которой принадлежит NP. Тогда для любого языка LÎNP : L< _P R , L^’ < _P R^’.

Докажем равенство классов NP и co- NP, показав их взаимное включение.

NP Í co-NP:Пусть LÎNP. Тогда L^’ Î co-NP. Применим к x Î L^‘сводящий алгоритм L^’ < _pR^’ , а результат на выходе подадим недетерминированной машине Тьюринга, вычисляющей проблему R^’,построенную композицию объявим машиной, вычисляющей язык L^’, откуда L^’ Î NP,

cледовательно, LÎ NP.

Co-NPÍ NP. Пусть L Î co-NP. Тогда существует полиномиальное сведение L^’к P, поскольку P является NP-полным, а L^’ принадлежит NP.

Это сведение является также сведением L к P^’. Цепочку x Î L подадим на вход сводящего алгоритма, выход которого подадим недетерминированной машине, вычисляющей P^’, полученную композицию объявим недетерминированной машиной, вычисляющей язык L, так что L Î NP.“

Упр стр 484