Изменения

В этой статье мы рассмотрим класс '''<tex>\mathrm{NP'''}</tex>-полных языков {{---}} '''<tex>\mathrm{NPC'''}</tex>.'''<tex>\mathrm{NPC''' }</tex> является одним из важнейших классов в теории сложности, так как если найдется язык из этого класса, который также входит в класс '''<tex>\mathrm{P'''}</tex>, тогда окажется, что '''<tex>\mathrm{P } = \mathrm{NP'''}</tex>.

Мы рассмотрим некоторые языки и докажем их '''<tex>\mathrm{NP'''}</tex>-полноту. Начнем мы с языка <tex> \mathrm{BH_{1N}} </tex>, так как к нему несложно сводятся все языки из '''<tex>\mathrm{NP'''}</tex>. Потом с помощью [[Сведение относительно класса функций. Сведение по Карпу. Трудные и полные задачи|сведений по Карпу]] будем сводить уже известные языки из '''<tex>\mathrm{NPC''' }</tex> к новым языкам, тем самым доказывая их '''<tex>\mathrm{NP'''}</tex>-трудность, а потом и '''<tex>\mathrm{NP'''}</tex>-полноту.Доказательство '''<tex>\mathrm{NP'''}</tex>-полноты будет состоять из двух пунктов: доказательство '''<tex>\mathrm{NP'''}</tex>-трудности и принадлежности языка классу '''<tex>\mathrm{NP'''}</tex>.

<tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex>, таких что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает '''<tex>1''' </tex> за время <tex> T(m, x) \le t </tex>.

# <tex> \mathrm{SAT}\in \mathrm{NP} </tex> <br>Можно написать недетерминированную программу <tex> p</tex>, которая распознает язык <tex> \mathrm{SAT} </tex>. Она будет недетерминированно выбирать подстановку, проверять , истинна ли формула при такой подстановке , и выдавать ответ: