143
правки
Изменения
м
→Лемма об эквивалентности PCP теоремы и NP-трудности GAP-3SAT: тег
Каждая строка <tex>Q_i</tex> дает нам <tex>C</tex> позиций в доказательстве и предикат <tex>\phi</tex>. <tex>\mathcal{R}</tex>
строит <tex>3CNF</tex> формулу для каждого <tex>\phi</tex>. Поскольку <tex>\phi</tex> функция от </tex>C</tex> пременных,
построенная <tex>3CNF</tex> содержит не более <tex>K=C2^C</tex> дизъюнктов. Для упрощения будем считать, что формула содержит
<tex>K</tex> дизъюнктов. <tex>\mathcal{R}</tex> возвращает конъюнкцию всех полученных формул, содержащую <tex>m=NK</tex> дизъюнктов.
