люється зведенням до неї .
Теорема 2.3. .
Доказ. Зіставимо будь-якій схемі в стандартному базисі таку 3-КНФ, здійснимість якої рівнозначна тому, що обчислюється схемою функція не дорівнює тотожно 0. У цю КНФ будуть входити всі змінні схеми ( і - використовуємо ті ж позначення, що і у визначенні схеми). Для цього побудуємо спочатку кон'юнкцію умов, що означають, що кожна з допоміжних змінних має значення, відповідне правій частині присвоювання < span align = "justify">. Є три типи таких умов (вони відпо трьом базисних функціях), і кожен можна записати у вигляді 3-КНФ:
В
Підставляючи ці 3-КНФ в , отримаємо 3-КНФ . Шукана 3-КНФ має вигляд . Дійсно, істинність рівносильна твердженням: всі присвоювання виконані правильно і в результаті вийшла 1 ( ). Значить, якщо при якихось значеннях змінних схема видає 1, то здійсненна, і навпаки.
Ще один простий приклад відомості.
Завдання ЦЛП (цілочисельного лінійного програмування). Дана система лінійних нерівностей з цілими коефіцієнтами. Чи є у неї цілочисельне рішення? (Іншими словами, совместна чи система?) p align="justify"> У цій задачі входом є матриця коефіцієнтів і вектор правих частин. Те, що , не зовсім очевидно. Виявляється, що в якості підказки Мерлін може повідомити Артуру значення змінних, при яких виконані всі нерівності системи. За визначенням, довжина цього повідомлення повинна бути також полиномиально обмежена. Можна довести, що з існування цілочисельного рішення слід існування цілочисельного рішення, розмір запису якого обмежений поліномом від довжини запису системи.
Зведемо тепер 3-КНФ до ЦЛП. Побудуємо за 3-КНФ систему лінійних нерівностей. Цілочисельних змінних візьмемо стільки ж, скільки є булевих змінних. Булевой змінної зіставимо вираз . Заперечення змінної зіставимо вираз . Кожній диз'юнкції ( - літерали) зіставимо нерівність , в якому , , - вирази, зіставлені ЛІТЕРАЛЬ диз'юнкції.
Шукана система містить для всіх нерівності , а також всі нерівності, зіставлені диз'юнкцій з КНФ. Очеви...
