Вопросы с тегом «pcp»

Вероятностно проверяемые доказательства

64
Каковы хорошие ссылки на понимание доказательства теоремы PCP?

Я знаком со многими результатами, в которых используется теорема PCP (главным образом в приближенных алгоритмах), но я никогда не сталкивался с четким объяснением теоремы PCP (то есть, что ).N P = P C P (O(log( н ) ) , O ( 1 ) )Nпзнак равнопСп(О(журнал⁡(N)),О(1))\mathsf{NP} =...

53
Существует ли тип щелевого усиления для задачи об изоморфизме графа?

Предположим, что и G 2 являются двумя неориентированными графами на множестве вершин { 1 , … , n } . Графы изоморфны тогда и только тогда, когда существует перестановка Π такая, что G 1 = Π ( G 2 ) , или более формально, если существует перестановка Π такая, что ( i , j ) является ребром в G 1...

36
Твердость аппроксимации без теоремы PCP

Важное применение теоремы PCP состоит в том, что она дает результаты типа «твердость приближения». В некоторых относительно более простых случаях такую ​​твердость можно доказать без PCP. Есть ли, однако, какой-либо случай, когда твердость результата аппроксимации была сначала доказана с...

20
Алгоритмы суперполиномиального приближения по времени для MAX 3SAT

Теорема PCP гласит, что для MAX 3SAT не существует алгоритма полиномиального времени, чтобы найти назначение, удовлетворяющее условиям 7/8 выполнимой формулы 3SAT, если только .P = N Р7 / 8 + ε7/8+ε7/8+ \epsilonпзнак равно Nппзнак равноNпP = NP Существует тривиальный алгоритм полиномиального...

17
Есть ли простой аргумент, который показывает, что гипотеза об уникальных играх подразумевает теорему PCP

как можно показать, какова связь между «гипотезой об уникальных играх» и «теоремой PCP»? Как объяснить, что «гипотеза об уникальных играх» является более сильной формой «теоремы...

15
Поддержание порядка в списке в за раз

Задача обслуживания заказа (или «поддержание заказа в списке») заключается в поддержке операций: singleton: создает список с одним элементом, возвращает указатель на него insertAfter: дает указатель на элемент, вставляет новый элемент после него, возвращает указатель на новый элемент delete: дает...

15
в пересчете на

Вероятностная система доказательств обычно называется ограничением M A , где Артур может использовать только f ( n ) случайных битов и может проверять только g ( n ) битов подтверждающий сертификат, присланный Мерлином (см. http://en.wikipedia.org/wiki/Interactive_proof_system#PCP ).пСп[ ф( н ) ,...

13
Существует ли непрерывная версия теоремы о параллельном повторении?

Теорема Раза о параллельном предсказании является важным результатом в PCP, аппроксимации и т. Д. Теорема оформилась следующим образом. Игра , где S , T , A , B - конечные множества, π - распределение по S × T и предикат V : S × T × A × B → { 0 , 1 } . Определить значение игры v ( G ) = max...

12
Жесткие пробелы в проблемах максимального удовлетворения ограничений?

Эквивалентная формулировка теоремы PCP является: Для Макса 3-SAT это -трудного различать выполнимые формулы и формулы , где не более группу фракций из пунктов являются выполнимы (для некоторого ).r r < 1NпNPNPрrrг < 1r<1r\lt 1 Существует ли какая-либо известная теорема о дихотомии, которая...

12
Техническая проблема с доказательством теоремы PCP

Отсюда я читаю доказательства и наткнулся на техническую (хотя и крайне важную) проблему. Я знаю, что это довольно специфично, и контекст проблематичен, но я не мог понять это сам. На страницах 51 и 55 после представления «стандартных» верификаторов они поворачиваются, чтобы модифицировать...

11
Теорема PCP - Шаг сокращения алфавита

То, что следует, может показаться глупым (и это, вероятно, отражает мое плохое понимание - поэтому, пожалуйста, потерпите меня) У меня был вопрос по теореме PCP. Мы знаем, что после первых трех шагов, а именно. Уменьшение степени, расширение и усиление разрыва, у нас есть граф ограничений с...

10
Односторонние ошибки в вероятностных системах доказательств

В большинстве вероятностных систем доказательства (например, теорема PCP) вероятности ошибок обычно определяются на стороне ложноположительных значений, т. Е. Типичное определение может выглядеть так: если то верификатор всегда принимает, но в другом случае вероятность отклонения составляет не...

9
Хорошие PCP для NP дают нам хороших PCP для всей полиномиальной иерархии?

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

9
Связь между PCP и L = SL

Книга Ароры и Барака содержит примечания к главе о PCP. Мы отмечаем, что общая стратегия Динура в некоторой степени напоминает зигзагообразную конструкцию графов расширителей и детерминистический алгоритм логарифмического пространства Рейнгольда для ненаправленной связи, описанный в главе 20, что...

9
Чисто теоретико-графическое объяснение редукции от уникального покрытия этикетки до Max-Cut

Я изучаю гипотезу об уникальных играх и известное сведение к Max-Cut из Khot et al. Из их статьи и из других источников в Интернете большинство авторов используют (что для меня является) неявную эквивалентность между сокращением MAX-CUT и созданием конкретных тестов для длинных кодов. Из-за моей...

9
Самые известные асимптотические размеры PCP / 3-SAT

Каковы наиболее известные асимптотические верхние оценки размеров вероятностно проверяемых доказательств? В идеале я ищу современное исследование по этому широкому вопросу, но если его нет, меня особенно интересует неприемлемость 3-SAT. Пусть 7/8 + ε-3-SAT будет 3-SAT с обещанием, что если 7/8 + ε...