UGC твердость предиката

Фон :

В оригинальной статье UGC Субхаша Хота ( PDF ) он доказывает, что UG-сложность определения того, допускает ли заданный экземпляр CSP ограничения всех форм Не-все-равные (a, b, c) по троичному алфавиту 1 - ограничений или не существует никаких заданий, удовлетворяющих $\epsilon$из ограничений, при сколь угодно маломе>0.$\frac{8}{9}+\epsilon$$\epsilon > 0$

Я интересно , был ли этот результат был обобщен для любой комбинации -ичных ограничений для л ≥ 3 и вариабельных доменов размера к ≥ 3 , где л ≠ к ≠ 3 . То есть,$\ell$$\ell \ge 3$$k \ge 3$$\ell \ne k \ne 3$

Вопрос :

Существуют ли какие-либо известные результаты твердости аппроксимации для предиката для x i ∈ G F ( k ) для ℓ , k ≥ 3 и ℓ ≠ k ≠ 3 ? $NAE(x_1, \dots, x_\ell)$$x_i \in GF(k)$$\ell, k \ge 3$$\ell \ne k \ne 3$

Меня особенно интересует комбинация значений ; например, предикат Не-все-равно ( x 1 , … , x k ) для x 1 … , x k ∈ G F ( k ) .$\ell = k$$x_1, \dots, x_k$$x_1 \dots, x_k \in GF(k)$

Я понял, что то, о чем я говорил выше, на самом деле известно.

Для и произвольного k ≥ 3 это содержится в работе Хота по FOCS 2002 «Твердость раскраски 3-раскрашиваемых 3-равномерных гиперграфов» (в действительности речь идет об общих $\ell = 3$$k \ge 3$$k$ , хотя название говорит только о 3-раскрашенном случае) ,

Для и k ≥ 2 на самом деле известна более высокая твердость. Даже если на самом деле присваивается переменным всего два значения, которые удовлетворяют всем ограничениям NAE (другими словами, ℓ- равномерный гиперграф может быть раскрашен с использованием 2 цветов без монохроматического гиперэджера), все равно найти NP трудно присваивание от размера домена k, который удовлетворяет как минимум 1 - 1 / k ℓ - 1 + ϵ ограничениям NAE (для произвольной постоянной ϵ > $\ell \ge 4$$k \ge 2$$\ell$$k$$1-1/k^{\ell-1}+\epsilon$$\epsilon > 0$). Это легко следует из того факта, что известный результат неприемлемости для гиперграфа 2-раскраски дает сильное утверждение плотности в случае надежности. Формальное утверждение появляется в моей статье SODA 2011 с Али Синопом «Сложность поиска независимых множеств в графах с ограниченной степенью (гипер) низкого хроматического числа» (лемма 2.3 в окончательной версии SODA и лемма 2.8 в более старой версии, доступной в ECCC http://eccc.hpi-web.de/report/2010/111/ ).

Я приземлился на этой странице из поиска о NAE-3SAT.

Я вполне уверен, что для задачи, которую вы задаете, должно быть NP-сложно определить, выполним ли экземпляр, или может быть удовлетворено не более доли ограничений. То есть, результат жесткой жесткости (совпадающий с тем, что достигается простым выбором случайного назначения) для удовлетворительных экземпляров, и нет необходимости в UGC.$1-1/k^{\ell-1}+\epsilon$

For $k=2$ and $\ell \ge 4$, this follows from Hastad's factor 7/8+epsilon inapproximability result for 4-set-splitting (which can then be reduced to k-set splitting for $k > 4$). If negations are okay, one can also use his tight hardness result for Max ($\ell-1$)-SAT.

For $k=\ell=3$, Khot proved this in a FOCS 2002 paper "Hardness of coloring 3-colorable 3-uniform hypergraphs." (That is, he removed the original UGC assumption.)

$\ell=3$$k\ge 3$$x_i+a,x_j+b,x_k$$a,b$

Для общего случая я не знаю, было ли это записано где-либо. Но если вам это действительно нужно, я, наверное, смогу что-то найти или проверить претензию.

Prasad Raghavendra in his STOC'08 Best Paper proved, assuming the Unique Games Conjecture, that a simple semidefinite programming algorithm gives the best approximation for any constraint satisfaction problem (including NAE) with constraints on constant number of variables each and with constant alphabet. To actually know what is the hardness factor for NAE, you need to understand how well the simple algorithm does for it, i.e., prove an integrality gap for the program. I don't know whether someone already did that for NAE in its full generality, or not.