143
правки
Изменения
м
ЗаметимПокажем, что для <tex>\mathrm{NP}</tex>-полной задачи <tex>3-Color</tex> существует сведение <tex>\mathcal{R}</tex> к <tex>GAP-3SAT_s</tex>.
→Лемма об эквивалентности PCP теоремы и NP-трудности GAP-3SAT: оговорка по фрейду
Сначала докажем, что из <tex>\mathrm{PCP}</tex> теоремы следует <tex>\mathrm{NP}</tex>-трудность <tex>GAP-3SAT_s</tex>.
Из принадлежности <tex>3Color</tex> <tex>\mathrm{NP}</tex> и <tex>\mathrm{PCP}</tex> теоремы следует, что существует
