о використовувати ті ж змінні, що і в доведенні теореми 1.2 (коди станів клітин таблиці обчислення). Щоб таблиця обчислення відповідала правильно проведеному успішному (з відповіддю "так") обчисленню, повинні виконуватися локальні правила узгодження для кожної четвірки клітин виду і результат повинен бути "так". Кожне таке правило задається формулою від змінних відповідають або розглянутої четвірці, або нульовою комірці самій нижній рядки таблиці. Визначимо формулу як кон'юнкцію всіх цих формул, в які підставлені значення змінних, що кодують вхід , доповнений символами до довжини . Значення, відповідні і , - константи, тому змінні, від яких залежить ця формула, відповідають і кодами внутрішніх елементів таблиці. Так що можна вважати, що формула залежить від і ще від якихось змінних, які ми позначимо .
Отже, ми зіставили слову формулу , яка з побудови має наступну властивість. Якщо виконується , то знайдеться такий набір значень , при якому істинна (ці значення описують роботу МТ на вході ). А якщо не виконується, то завжди помилкова (оскільки по суті стверджує, що обчислення на вході дає відповідь "так"). Таким чином, при така формула іноді (при деяких значеннях ) істинна, при - завжди помилкова.
Інші приклади NP-повних задач виходять за допомогою наступної леми.
Лемма 2.2. Якщо і , то - NP-повна. І взагалі, якщо - NP-повна, і , то - NP-повна.
Доказ. Досить перевірити транзитивність сводимости: якщо , , то . Вона випливає з того, що композиція двох полиномиально вичіслімих функцій полиномиально вичіслімих.
-КНФ. Здається предикатом
є 3-КНФ, яка істинна істинна при деяких значеннях змінних. 3-КНФ - це кон'юнкція диз'юнкцій, кожна з яких містить три литерала.
також NP-повна. Це встанов...
