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

9

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

Пусть 7/8 + ε-3-SAT будет 3-SAT с обещанием, что если 7/8 + ε доля предложений выполнима, то экземпляр является выполнимым. Каковы наиболее известные сокращения 3-SAT сnпункты к 7/8 + ε-3-SAT? Например, есть ли сокращение с помощьюO(nlogn)пункты? (O(n)пункты является открытой проблемой.) Уменьшение равномерного квазилинейного размера NC? Какова зависимость отεв том числе, когда ε0? Есть ли известный линейный размер (зависит отε) сокращение (1-ε) -3-SAT до 7/8 + ε-3-SAT, и если нет, то есть ли у нас лучшие оценки для (1-ε) -3-SAT? Даже частичный ответ будет интересным.

Кроме того, хотя это, возможно, сделало бы вопрос слишком широким, я должен упомянуть, что другой важной проблемой здесь являются постоянные факторы, которые из-за таких методов, как длинный код, обычно невероятно велики.

Дмитрий Тарановский
источник

Ответы:

7

Современное состояние для РСР, которые обеспечивают снижение до (78+ε) 3-SAT (даже для субконстант ε) те из Даны Мошковиц и Ран Раз , которые имеют длинуn1+o(1), Однако я не знаю, пытался ли кто-нибудь вычислить точную зависимость длины отεили сложность вычисления редукции. Их основной технический результат был позже упрощен Ирит Динур и Прахлад Харша .

Если вас интересуют короткие PCP с постоянным количеством запросов, которые не обязательно дают оптимальное снижение жесткости аппроксимации (иначе говоря, «PCP с высокой ошибкой»), то современный результат - это PCP длины npolylognблагодаря Эли Бен-Сассону и Мадху Судану и его улучшению Динур . Опять же, я не знаю, кто-нибудь, какова точная сложность вычисления сокращения.

Или меир
источник
Спасибо; Обе части были полезны. Я понял, что PCP квазилинейного размера с O (1) запросами и постоянной ошибкой остается открытой проблемой.
Дмитрий Тарановский
Нет, это на самом деле следует из работ Бен-Сассона и Судана. Получение таких PCP с непостоянной ошибкой является открытой проблемой.
Или Меир
1
Я посмотрел еще немного, и Dinur 2007 расширяет статью, которую вы цитировали во втором абзаце, чтобы показатьSATPCP12,1[log2n+O(loglogn),O(1)], Если я правильно понимаю, это подразумевает уменьшение 3-SAT до некоторого квазилинейного размера1ε 3-SAT, но результат, который вы цитировали в первом абзаце, не является избыточным, потому что он дает нам 7/8+εи более.
Дмитрий Тарановский
Да, это правильно. Я забыл упомянуть результат Динура, я добавлю его в ответ.
Или Меир