Является ли Gap-3SAT NP-полным даже для формул 3CNF, в которых пара переменных не встречается в значительно большем количестве предложений, чем в среднем?

32

В этом вопросе формула 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 1x 2x 4 ) ∧ (¬x 1 ∨¬x 3x 4 ) ∧ ( x 1x 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

Цуёси Ито
источник
@ Tsuyoshi: я прав, предполагая, что ничего не известно о других промежуточных случаях, между и ? m=O(n)m=Ω(n3)
Андрас Саламон
1
@ Андрас: Я не знаю каких-либо предыдущих результатов о промежуточных случаях, но у меня есть то, что я считаю доказательством NP-полноты следующих случаев. (1) Попарно ограниченные, предложения, но без пробела. (2) С пробелом, предложений для любой константы d <3, но не обязательно попарно ограниченной. (3) С пробелом, попарно ограниченным, предложения для любой константы d <2. Доказательство (1) является простым сокращением из [Fei98]. Доказательство (2) использует часть результата Ailon and Alon 2007 . В доказательстве (3) используются расширители. Ω(n2)Ω(nd)Ω(nd)
Цуёси Ито
1
@Tsuyoshi: с нетерпением жду чтения вашей газеты.
Андрас Саламон
4
У меня нет ответа, но я бы проверил, могут ли методы, удостоверяющие, что случайный 3CNF из m предложений является неудовлетворительным, удастся показать, что эта проблема проста, по крайней мере, если вы требовали, чтобы точность была близка к 7/8. Эти работы завершаются успешно, если имеется более предложений и были распространены на полуслучайные модели (см. Feige FOCS 07 об опровержении сглаженного 3CNF). Тем не менее, кажется, что Tsuyoshi показал, что даже случай здесь все еще NP-труден, так что, возможно, это показывает, что эти работы не актуальны. sn1.5n1.9
Вооз Барак
7
Во всяком случае, вы всегда можете «уплотнить» экземпляр 3SAT, заменив каждую переменную на копий, а затем заменив каждое предложение на предложений, заменяя каждую переменную в исходном предложении на копии всеми возможными способами. Это дает вам пример, в котором выполнима та же часть предложений, что и прежде, но вы переходите от n переменных и m предложений к nM переменным и , поэтому, не ограничивая количество вхождений, вы можете сохранить обоснованность даже в формулах с переменными и предложениями. MM3mM37/8+ϵNN2.999
Лука Тревизан

Ответы:

6

Не полный ответ, но, надеюсь, близко. Это очень близко к комментариям Луки выше. Я полагаю, что ответ состоит в том, что, по крайней мере, существуют константы B ∈ ℕ, a > 0 и 0 < s <1, такие что Gap-3SAT s является NP-полной даже для формулы 3CNF, которая попарно B- ограничена и состоит из по крайней мере для любой константы . ϵan2ϵϵ

Доказательство состоит в следующем. Рассмотрим экземпляр GAP-3SAT для переменных, в котором каждая переменная появляется не более 5 раз. Это NP-полная, как вы говорите в вопросе. ϕ NsϕN

Теперь мы создаем новый экземпляр следующим образом:Φ

  1. Для каждой переменной в , имеет переменных .xiϕΦnyij
  2. Для каждого набора индексов , и с , имеет пару предложений и . Я буду ссылаться на них как на условия сравнения, так как они гарантируют, что если они удовлетворены.iababΦyiayibyibyibyiayiayia=yib
  3. Для каждого предложения в действующего на переменные , и , для каждого и , содержит эквивалентное предложение, где заменяется на , заменяется на и заменяется на (здесь сложение выполняется по модулю ). Я буду ссылаться на них как на унаследованные.ϕxixjxkabΦxiyiaxjyjbxkyk(a+b)n

Общее количество переменных тогда равно . Примечание. У есть предложений сравнения и унаследованных предложений, в общей сложности предложений. Принимая мы имеем и общее количество предложений . Мы берем , поэтому .m=nNΦ2Nn253Nn2113Nn2n=Nkm=Nk+1C=113N2k+1=113m21k+1k=ϵ11Cm2ϵ

Далее, попарно 8-ограничен (максимум 2 из предложений сравнения и 6 из унаследованных предложений).Φ

Наконец, если неудовлетворительно, то по крайней мере предложений являются неудовлетворительными. Теперь, если для любого то по крайней мере предложений не удовлетворяются. Обратите внимание, что для удовлетворения неудовлетворенных предложений в наборе унаследованных предложений для фиксированных необходимо присвоение переменных , и должны отличаться по крайней мере позиций, оставляя по крайней мере сравнений неудовлетворительными предложениями. Это должно выполняться для каждого выбора иϕ(1s)Nyiayiba,bn1(1s)Na,by:ay:by:(a+b)1s5N1s5N(n1)abпоэтому, по крайней мере, условия сравнения должны оставаться в целом неудовлетворенными, чтобы удовлетворять достаточное количество унаследованных предложений. Однако если вы посмотрите на другой крайний случай, когда все условия сравнения выполняются, то пункты являются неудовлетворительными. Следовательно, разрыв остается (хотя и сокращается) при .1s5Nn2=3(1s)11C(1s)Nn2=(1s)m2k+1k+1=(1s)Cs=4+s5

Константы, вероятно, должны быть дважды проверены.

Джо Фитцсимонс
источник
Спасибо, Джо. Извините, если это неясно, но в этом вопросе я требую, чтобы все три переменные в каждом предложении были различны, и поэтому нельзя сравнивать предложения сравнения в том виде, в котором они написаны. У меня есть доказательство того же факта (попарно ограниченные, Ω (n ^ (2 − ε)) предложения с пробелом), которое использует графы расширителей, но если это можно доказать без использования расширителей, я очень заинтересован.
Цуёси Ито
@ Tsuyoshi: Ах, я вижу. На самом деле, я изначально доказал это самому себе с помощью различных переменных, поэтому очень легко настроить его в нужной форме. Вы просто назначаете предложения сравнения по-разному. Вместо двух пунктов, которые я дал, вам нужно 4: , , и . Ясно, что они сводятся к тем же 2 переменным предложениям, что и раньше. Очевидно, это изменяет константы, но не имеет никакого другого значения. yiayibyi(a+b)yiayibyi(a+b)yiayibyi(a+b)yiayibyi(a+b)
Джо Фитцзимонс
Возможно, есть способ обойти фактор , взяв , хотя наиболее наивная реализация этого дает случаи, которые растут очень немного быстрее, чем полиномиально. k = k ( n )ϵk=k(n)
Джо Фитцсимонс
Я проверю детали более тщательно позже, но идея использования a, b и (a + b), кажется, работает. Это должно освободить меня от явной работы с экспандерами. Благодарность!
Цуёси Ито
Нет проблем. Рад, что мог помочь.
Джо Фицсимонс