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

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

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

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

Современное состояние для РСР, которые обеспечивают снижение до $(\frac{7}{8}+\varepsilon)$ 3-SAT (даже для субконстант $\varepsilon$) те из Даны Мошковиц и Ран Раз , которые имеют длину$n^{1 + o(1)}$, Однако я не знаю, пытался ли кто-нибудь вычислить точную зависимость длины от$\varepsilon$или сложность вычисления редукции. Их основной технический результат был позже упрощен Ирит Динур и Прахлад Харша .

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