Оглавление
Вероятностно проверяемое доказательство
-
Определение вероятностно проверяемого доказательства (PCP)
- PCP – это тип доказательства, которое может быть проверено с помощью рандомизированного алгоритма.
- Алгоритм должен принимать правильные доказательства и отклонять неправильные с высокой вероятностью.
- Стандартное доказательство также удовлетворяет этим требованиям, но использует все доказательство целиком.
-
Интересность вероятностно проверяемых доказательств
- PCP позволяет проверять доказательства, прочитав лишь несколько фрагментов.
- Они приводят к появлению множества классов сложности, зависящих от количества запросов и степени случайности.
-
Теорема PCP и её значение
- Теорема PCP утверждает, что PCP[O(log n),O(1)] = NP.
- Теория PCP изучает возможности вероятностно проверяемых систем доказательств и находит применение в вычислительной сложности и криптографии.
-
История и значение теории PCP
- Определение вероятностно проверяемых доказательств было введено Аророй и Сафрой в 1992 году.
- Бабай, Фортноу и Лунд доказали в 1990 году, что PCP [poly(n), poly(n)] = NEXP.
- Теорема PCP и MIP = NEXP являются важными результатами в теории сложности вычислений.
-
Свойства вероятностно проверяемых доказательств
- При экстремальных настройках параметров PCP эквивалентно стандартным классам сложности.
- Линейный PCP имеет важное применение в системах проверки подлинности.
-
Рекомендации и внешние ссылки
- Ссылки на конспекты курсов и статьи по теме PCP предоставлены для дополнительного изучения.
Полный текст статьи: