gn = "justify">, що .
сводимости по Карпу також називають поліноміальною сводимости, а часто - просто схожа.
Лемма 2.1. Нехай . Тоді
В В
.
Доказ. Пункт 1 зовсім очевидний - щоб обчислити значення предиката , досить застосувати до входу функцію , а до результату її роботи - програму обчислення .
Пункт 2 випливає з пункту 1.
Пункт 3 також простий. Його можна пояснювати по-різному. Наприклад, так: Мерлін повідомляє Артуру (довжина якої обмежена деяким поліномом від довжини , оскільки ) і слово , яке переконує Артура в тому, що . Артур також може перевірити, що йому дійсно повідомлено . Використовуючи визначення 2.2, можна написати ланцюжок еквівалентностей
В
Поліном в останньому виразі - це композиція поліномів і .
Визначення 2.5. Предикат називається NP-повним, якщо будь-який предикат з до нього зводиться.
Якщо деякий NP-повний предикат можна обчислювати за час , то будь-який предикат з NP можна обчислювати за час для деякого фіксованого числа . Така втрата ефективності вважається в цій науці несущественной.полние предикати існують, наведемо приклади.
Здійснимість. Здається предикатом
є формула з булевими змінними і символами , яка істинна при деяких значеннях змінних.
Теорема 2.2 (Кук, Левін). 1) , 2) - NP-повна.
Якщо , то .
Доказ (теореми 2.2). 1) Мерліну досить повідомити Артуру значення змінних, що входять у формулу, за яких вона істинна. Артур впорається з перевіркою істинності отриманого висловлювання. p align="justify">) Нехай предикат з NP, який потрібно звести до , має вигляд .
Розглянемо таблицю обчислення (див. доведення теореми 1.2) для МТ, що обчислює (входом є пара ). Будем...
