Теорема PCP утверждает, что каждая проблема решения в NP имеет вероятностно проверяемые доказательства (или, что то же самое, что существует полная и квази-звуковая система доказательств для теорем в NP, использующая постоянную сложность запроса и логарифмически много случайных битов).
«Народная мудрость», окружающая теорему PCP (на мгновение игнорируя важность PCP для теории приближений), состоит в том, что это означает, что доказательства, написанные на строгом математическом языке, могут быть эффективно проверены с любой желаемой степенью точности без необходимости чтения всего доказательство (или большая часть доказательства вообще).
Я не в состоянии понять это. Рассмотрим расширение второго порядка для логики высказываний с неограниченным использованием квантификаторов (которые, как мне сказали, уже слабее ZFC, но я не логик). Мы уже можем начать выражать теоремы, которые недоступны для NP чередующимися кванторами.
Мой вопрос заключается в том, существует ли простой, известный способ «развертывания» кванторов в пропозициональных утверждениях более высокого порядка, так что PCP для теорем в NP применимы одинаково хорошо для любого уровня PH. Вполне возможно, что этого нельзя сделать - что развертывание квантификатора в худшем случае будет стоить некоторой постоянной части надежности или правильности нашей системы доказательств.
источник
Ответы:
Истина утверждения отличается от того, что оно имеет (краткое) доказательство в системе доказательств. Язык выразителен, но это не означает, что все действительные утверждения в языке имеют короткие доказательства в системе.
Теорема не говорит, что вы можете проверить истинность утверждения или даже правильность произвольного длинного доказательства или произвольных теорем. Это для доказательства членства вН П набор, который по определению имеет полиномиальный размер доказательств (сертификатов) членства. Теорема говорит только о том, что вам не нужно читать полное (полиномиальное) доказательство принадлежности кН П установить, чтобы решить его правильность.
Одним из следствий теоремы является ее применение к набору теорем на произвольном языке, который имеет короткие (т. Е. Произвольные полиномиальные) доказательства в эффективной системе доказательств (т. Е. Разрешимо за полиномиальное время, если данная строка является доказательством заданной заявление). Например, теоремы ZFC, которые имеют доказательства размераN100 где N это размер формулы. Если система доказательств надежна, то вы можете вероятностно проверить правильность теорем, которые имеют короткие доказательства, прочитав небольшую часть их доказательств. Я думаю, что в этом и заключается смысл неформального утверждения « доказательства, написанные на строгом математическом языке, могут быть эффективно проверены с любой желаемой степенью точности без необходимости чтения всего доказательства ».
источник
Позвольте мне попытаться уточнить.
Рассмотрим следующую вычислительную задачу: учитывая математическое утверждение (в вашей любимой системе аксиом) и число n, заданное в унарном представлении, решите, имеет ли утверждение доказательство размера n.
Это проблема NP: при наличии доказательства можно эффективно проверить, что он имеет размер n и является правильным доказательством теоремы. Примечание: даже если оператор включает квантификаторы, такие как FOR ALL, это не означает, что верификатор должен проверять все возможности, это просто означает, что верификатор использует правила вывода, которые включают квантификатор FOR ALL.
Таким образом, теорема PCP применима к этой проблеме, и поэтому существует (другой) формат доказательства, который допускает вероятностную проверку.
Еще одно замечание (относительно замечания Питера): верификатор PCP использует только логарифмическую случайность. Это означает, что его можно заменить стандартным детерминированным верификатором, который рассматривает все доказательство. То есть наличие PCP-верификатора для языка помещает его в NP.
источник