Направлено на неспециалистов-компьютерщиков:
Теорема PCP гласит, что вы можете создавать доказательства, которые так легко проверить, что вам нужно только смотреть на постоянное количество (случайно выбранных) битов, чтобы (обычно) отличить плохое доказательство от хорошего.
Направлено на теоретика-мирянина:
То, что язык находится в NP, означает, что вы можете доказать , строка на языке легко. Например, вы можете доказать, что логическая схема является удовлетворительной, предоставив ее удовлетворительный ввод. (но трудно доказать, что схема не удовлетворительная!)
В этом контексте проверяющее доказательство лицо / программа / машина Тьюринга должны работать за полиномиальное время (в размере строки, предположительно в языке). Это должно быть complete , означающее, что оно всегда принимает действительное доказательство того, что данная строка находится на языке. Это должен быть sound , что означает, что он отвергает любое «доказательство» для строки, которая не в языке.
Для NP верификатор является детерминированным. Что если верификатор может использовать случайность? Затем мы должны допустить некоторую ошибку, поэтому мы позволяем верификатору не быть полностью звуком - он может неправильно принять некоторые доказательства. На самом деле все, что нас волнует, это то, что проверяющий обнаруживает плохие доказательства, по крайней мере, в 1/4 времени. Если вам нужна лучшая точность, вы всегда можете запустить ее еще несколько раз! : -)
Теорема PCP, в ее самой сильной форме, говорит, что любой язык в NP имеет систему доказательства, которую можно проверить, только взглянув на константу количество случайно выбранных битов. Константа ... 3 . (Это те же 3 из 3-SAT). В этих доказательствах используются коды с исправлением ошибок, так что любая ошибка в доказательстве будет конфликтовать с большой частью входных данных. Использование более сильного кода позволяет получить произвольно близкое к 50% звучание всего за 3 бита.