В этом вопросе формула 3CNF означает формулу CNF, в которой каждое предложение включает ровно три различные переменные. Для константы 0 < s <1 Gap-3SAT s является следующей проблемой обещания:
GAP-3sat сек
экземпляра : а 3CNF формула φ.
Да-обещание : φ выполнимо.
Нет-обещание : Нет истину назначение удовлетворяет более чем ей доля из пунктов ф.
Один из эквивалентных способов сформулировать знаменитую теорему PCP [AS98, ALMSS98] состоит в том, что существует постоянная 0 < s <1 такая, что Gap-3SAT s является NP-полной.
Мы говорим, что формула 3CNF попарно B-ограничена, если каждая пара различных переменных присутствует не более чем в B предложениях. Например, формула 3CNF ( x 1 ∨ x 2 ∨ x 4 ) ∧ (¬x 1 ∨¬x 3 ∨ x 4 ) ∧ ( x 1 ∨ x 3 ∨¬x 5 ) попарно 2-ограничена, но не попарно 1 ограничено, потому что, например, пара ( x 1 , x 4 ) появляется в более чем одном предложении.
Вопрос . Существуют ли константы B ∈ ℕ, a > 0 и 0 < s <1 такие, что Gap-3SAT s является NP-полной даже для формулы 3CNF, которая попарно B- ограничена и состоит по крайней мере из 2-х предложений, где n такое количество переменных?
Попарная ограниченность ясно подразумевает, что существуют только O ( n 2 ) предложений. Вместе с квадратичной нижней границей количества предложений это примерно говорит о том, что ни одна пара отдельных переменных не появляется в значительно большем количестве предложений, чем в среднем.
Для Gap-3SAT известно, что редкий случай сложен : существует постоянная 0 < s <1, такая, что Gap-3SAT s является NP-полной даже для формулы 3CNF, где каждая переменная встречается ровно пять раз [Fei98]. С другой стороны, плотный случай прост : Max-3SAT допускает PTAS для формулы 3CNF с Ω ( n 3 ) различными предложениями [AKK99], и поэтому Gap-3SAT s в этом случае находится в P для каждой константы 0 < с <1. Вопрос касается середины этих двух случаев.
Вышеупомянутый вопрос первоначально возник при изучении квантовой вычислительной сложности, более конкретно, двухпроцессорных односторонних интерактивных систем доказательства с запутанными проверяющими (системы MIP * (2,1) ). Но я думаю, что вопрос может быть интересным сам по себе.
Ссылки
[AKK99] Санджив Арора, Дэвид Каргер и Марек Карпински. Схемы аппроксимации полиномиального времени для плотного случая NP-трудных задач. Журнал компьютерных и системных наук , 58 (1): 193–210, февраль 1999 г. http://dx.doi.org/10.1006/jcss.1998.1605
[ALMSS98] Санджив Арора, Карстен Лунд, Раджив Мотвани, Мадху Судан и Марио Сегеды. Доказательство проверки и сложности аппроксимации проблемы. Журнал ACM , 45 (3): 501–555, май 1998 г. http://doi.acm.org/10.1145/278298.278306
[AS98] Санджив Арора и Шмуэль Сафра. Вероятностная проверка доказательств: новая характеристика Н.П. Журнал ACM , 45 (1): 70–122, январь 1998 г. http://doi.acm.org/10.1145/273865.273901
[Fei98] Уриэль Фейдж. Порог ln n для аппроксимации заданного покрытия. Журнал ACM , 45 (4): 634–652, июль 1998 г. http://doi.acm.org/10.1145/285055.285059
Ответы:
Не полный ответ, но, надеюсь, близко. Это очень близко к комментариям Луки выше. Я полагаю, что ответ состоит в том, что, по крайней мере, существуют константы B ∈ ℕ, a > 0 и 0 < s <1, такие что Gap-3SAT s является NP-полной даже для формулы 3CNF, которая попарно B- ограничена и состоит из по крайней мере для любой константы . ϵan2−ϵ ϵ
Доказательство состоит в следующем. Рассмотрим экземпляр GAP-3SAT для переменных, в котором каждая переменная появляется не более 5 раз. Это NP-полная, как вы говорите в вопросе. ϕ Ns ϕ N
Теперь мы создаем новый экземпляр следующим образом:Φ
Общее количество переменных тогда равно . Примечание. У есть предложений сравнения и унаследованных предложений, в общей сложности предложений. Принимая мы имеем и общее количество предложений . Мы берем , поэтому .m=nN Φ 2Nn2 53Nn2 113Nn2 n=Nk m=Nk+1 C=113N2k+1=113m2−1k+1 k=ϵ−1−1 C∝m2−ϵ
Далее, попарно 8-ограничен (максимум 2 из предложений сравнения и 6 из унаследованных предложений).Φ
Наконец, если неудовлетворительно, то по крайней мере предложений являются неудовлетворительными. Теперь, если для любого то по крайней мере предложений не удовлетворяются. Обратите внимание, что для удовлетворения неудовлетворенных предложений в наборе унаследованных предложений для фиксированных необходимо присвоение переменных , и должны отличаться по крайней мере позиций, оставляя по крайней мере сравнений неудовлетворительными предложениями. Это должно выполняться для каждого выбора иϕ (1−s)N yia≠yib a,b n−1 (1−s)N a,b y:a y:b y:(a+b) 1−s5N 1−s5N(n−1) a b поэтому, по крайней мере, условия сравнения должны оставаться в целом неудовлетворенными, чтобы удовлетворять достаточное количество унаследованных предложений. Однако если вы посмотрите на другой крайний случай, когда все условия сравнения выполняются, то пункты являются неудовлетворительными. Следовательно, разрыв остается (хотя и сокращается) при .≈1−s5Nn2=3(1−s)11C (1−s)Nn2=(1−s)m2k+1k+1=(1−s)C s′=4+s5
Константы, вероятно, должны быть дважды проверены.
источник