Изменения

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

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

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