Имеются два персонажа: король Arthur (Артур), умственные способности которого полиномиально ограничены, и волшебник Merlin (Мерлин), который интеллектуально всемогущ и знает правильные ответы на все вопросы. Король A интересуется некоторым свойством (например, "есть ли у графа гамильтонов цикл"), а волшебник M хочет, чтобы король признал наличие этого свойства (ну, скажем, граф стремится к званию гамильтонова и дал M взятку). A не доверяет своему волшебнику, зная его корыстолюбие, и хочет иметь возможность самостоятельно проверить предложенный M ответ.
Поэтому они действуют следующим образом. A и M оба смотрят на слово x, после чего M сообщает некоторую информацию (слово y), которая должна убедить A, что L(x)=1. Используя эту информацию, A проверяет убедительность аргументов M некоторым полиномиальным способом.
В этих терминах определение класса NP можно сформулировать так: свойство L принадлежит классу NP, если у Артура есть полиномиальный способ проверять убедительность доводов Мерлина, причем:
L(x)=1 => у M есть способ убедить A в этом;
L(x)=0 => как бы M ни изощрялся, A не поверит, что L(x)=1.
