Tvp-полнота - Большая Энциклопедия Нефти и Газа, статья, страница 1
И волки сыты, и овцы целы, и пастуху вечная память. Законы Мерфи (еще...)

Tvp-полнота

Cтраница 1


Строгое доказательство TVP-полноты проблемы ВЫПОЛНИМОСТЬ требует привлечения понятий недетерминированной машины Тьюринга и полиномиального вычисления на такой машине, что выходит за рамки данной брошюры. Проблема 2 - ВЫП получается из проблемы ВЫПОЛНИМОСТЬ, если в последней рассмотреть лишь такие КНФ, у которых каждый конъюнктивный сомножитель содержит не более двух переменных. Аналогичным образом определяется проблема 3 - ВЫП. Далее мы докажем, что проблема 2 - ВЫП полиномиально разрешима ( это означает, в частности, что проблема 2 - ВЫП не является проблемой переборного типа), а проблема 3 - ВЫП TVP-полна.  [1]

Аналогично можно доказать TVP-полноту задач частичной ZV - и Fz-квазиотделимости.  [2]

Исторически первое доказательство NP-полноты было предложено Куком для задачи о выполнимости схемы. Метод сведения за полиномиальное время был предложен Карпом ( Richard Karp) и использован им для доказательства TVP-полноты целого ряда задач.  [3]



Страницы:      1