Пример для нетривиального проверки PCP для проблемы NP-полного

Question

Во время моего участия в курсе по борьбе с проблемами NP-высоты я столкнулся с теоремой PCP, заявляя

$ qquad displaystyle mathsf {np} = mathsf {pcp} ( log n, 1) $.

Я понимаю техническое определение проверки PCP, поэтому я в принципе знаю, какой алгоритм должен существовать для каждой проблемы NP: рандомизированный алгоритм, который проверяет $ O (1) $ биты данного сертификата для данного ввода, используя $ O ( log n) $ случайные биты, так что этот алгоритм является по сути односторонней ошибкой Monte-Carlo Verifier.

Тем не менее, у меня возникают проблемы с представлением о том, как такой алгоритм может иметь дело с проблемой NP-полной. Через за исключением прочтения доказательства теоремы PCP, существуют ли конкретные примеры для таких алгоритмов?

Я снял соответствующие разделы Вычислительная сложность: современный подход Арора и Барак (2009), но ничего не нашел.

Пример с использованием $ mathsf {pcp} ( _, ll n) $ алгоритм будет в порядке.

Answer 1

Следуя комментарию SDCVVC Я проверил пример 11.7 в Вычислительная сложность: современный подход Арора и Барак (Черновик 2008). Там авторы описывают «алгоритм PCP» для проблемы График неизоморфизм (GNI):

Вход: Два графика $ g_0 $ и $ g_1 $ с вершинами $ n $.

Выход: Принять, если и только тогда, когда $ g_0 $ и $ g_1 $ не являются изоморфными (напишите $ g_0 not equiv g_1 $).

Мы обозначаем сертификат (они называют его «доказательством») по $ pi $ и с $ pi (i) $ $ i $-th $ pi $.

Алгоритм $ a $ доходы следующим образом:

• Выберите немного $ b in {0,1 } $ равномерно случайно.
• Выберите перестановку $ sigma in s_n $ (из вершин $ g_b $).
• Принять, если $ pi ( langle sigma (g_b) rangle) = b $, отвергните иное.

Здесь, $ langle _ rangle $ является некоторой вычислительной биением от $ mathbb {n}^n $ в подходящий диапазон $ [0..n] subteq mathbb {n} $. Мы предполагаем, что если не существует Derefence Bit в $ pi $, то есть сертификат слишком короткий, мы отклоняем.

Требовать: По вышеуказанному алгоритму GNI находится в $ OperatorName {pcp} (n log n, 1) $, т.е.

1. Алгоритм использует $ o (n log n) $ случайные биты и запросы $ o (1) $ биты $ pi $,
2. $ (G_0, g_1) in mathrm {gni} $ подразумевает, что есть какой -то сертификат $ pi $, так что $ pr [a (g_0, g_1, pi) tex
3. $ (G_0, g_1) notin mathrm {gni} $ подразумевает, что $ pr [a (g_0, g_1, pi) text {отклонить}] geq tfrac {1} {2} $ for все Сертификаты $ pi in {0,1 }^*$.

AD 1: Ясно из алгоритма, отметив, что однородная выборка перестановки возможна с помощью $ abx n log n $ случайными битами.

AD 2: Рассмотрим сертификат

$ qquad displaystyle pi ( langer h rangle) = begin {case} 0 &, h aquiv g_0, h not equiv g_1 1 &, h aquiv g_1, h aviv g_0 text {Artrary} &, text {иной} end {case} $

где $ H $ - все графики с узлами $ n $. Поскольку $ g_0 not equiv g_1 $ и $ sigma (g_b) equiv g_b $, у нас есть $ sigma (g_b) not equiv g_ {1-b} $ для всех $ b $ и $ sigma $ Анкет Поэтому запрос $ pi $ всегда дает $ b $ и, следовательно, всегда принимает.

AD 3: Пусть $ pi in {0,1 }^*$ Arbitrary и $ h = sigma (g_b) $ Выбранный график запроса. Если наш запрос попадает в несуществующий бит $ pi $, мы отклоняем по допущению, что является правильным. В противном случае мы рассчитываем

$ qquad begin {align} pr [ text {Accement}] & = pr [b = 0] cdot frac {#[ pi (h) = 0 mid h aquiv g_0]} { #[H equiv g_0]} + pr [b = 1] cdot frac {#[ pi (h) = 1 mid h aquiv g_1]} {#[h equiv g_1]} & = frac {1} {2} cdot Left ( frac {#[ pi (h) = 0 mid h aquiv g_0]} {#[h aquiv g_0]} + frac {#[ pi (h) = 1 mid h aquiv g_0]} {#[h aquiv g_0]} right) & = frac {1} {2} end {align} $ Использование этого $ h equiv g_1 iff h equiv g_0 $ в этом случае.

Таким образом, требование доказано.

---

Некоторые наблюдения, которые помогли мне лучше понять эти понятия.

• Сертификат $ pi $ может быть произвольно длинным и произвольно сложным. Обратите внимание, что «хорошие» сертификаты для вышеуказанного алгоритма по существу решают ту же проблему, что и алгоритм (много раз).
• Но это не означает, что любая проблема решения может быть решена в стиле PCP, «просто предоставив ответ в сертификате». Условие 3 предотвращает любую наивную попытку такого рода.
• В целом невозможно получить эффективный (рандомизированный односторонний ошибка) алгоритм, который угадывает сертификат (как в случае с NP-сертификационными проверками).

---

1. Строго говоря, это предполагает, что $ n! = 2^k $ (который, конечно, почти никогда не имеет), так как мы иметь бесконечный худший случай выполнения за другие $ n $. Тем не менее, Арора/Барак, кажется, игнорируют этот аспект.

Answer 2

Две проблемы, которые могут помочь развивать интуицию:

1. Докажите, что $ mathsf {am} subseteq mathsf {pcp} ( text {poly} (n), 1) $. Вам разрешено предположить $ mathsf {np} subseteq mathsf {pcp} ( text {poly} (n), 1) $.

2. Докажите, что $ mathsf {pspace} subseteq mathsf {pcp} ( text {poly} (n), text {poly} (n)) $. Намекать:

Используйте ip = pspace

Виктори: первое упражнение подчиняется PCP для GNI, а второй подчиняется PCP для постоянного. Оба результата подчиняются $ mathsf {nexp} = mathsf {pcp} ( text {poly} (n), 1) $.