UGC-Härte des Prädikats

Hintergrund :

In Subhash Khots Original-UGC-Arbeit ( PDF ) beweist er die UG-Härte der Entscheidung, ob eine gegebene CSP-Instanz mit Einschränkungen aller Formen, die nicht alle gleich sind (a, b, c), über ein ternäres Alphabet eine Zuordnung zulässt, die 1 erfüllt - der Auflagen oder ob keine Auflagen vorliegen, die 8 erfüllen$\epsilon$der Nebenbedingungen, für beliebig kleinesϵ>0.$\frac{8}{9}+\epsilon$$\epsilon > 0$

Ich bin gespannt , ob dieses Ergebnis für eine beliebige Kombination von verallgemeinerte ary Einschränkungen für l ≥ 3 und variablen Domänen der Größe k ≥ 3 wobei l ≠ k ≠ 3 . Das ist,$\ell$$\ell \ge 3$$k \ge 3$$\ell \ne k \ne 3$

Frage :

Gibt es eine bekannte Härte der Approximationsergebnisse für das Prädikat für x i ∈ G F ( k ) für ℓ , k ≥ 3 und ℓ ≠ k ≠ 3 ? $NAE(x_1, \dots, x_\ell)$$x_i \in GF(k)$$\ell, k \ge 3$$\ell \ne k \ne 3$

Mich interessiert vor allem die Wertekombination ; zB das Prädikat Nicht alle gleich ( x 1 , … , x k ) für x 1 … , x k ∈ G F ( k ) .$\ell = k$$x_1, \dots, x_k$$x_1 \dots, x_k \in GF(k)$

Mir wurde klar, dass das, was ich oben behauptet hatte, tatsächlich bekannt ist.

Für und beliebiges k ≥ 3 ist dies in Khots FOCS 2002-Papier "Härte der Färbung von 3-färbbaren 3-einheitlichen Hypergraphen" (das Papier spricht tatsächlich von allgemeinem k , obwohl der Titel nur über den 3-färbbaren Fall spricht). .$\ell = 3$$k \ge 3$$k$

Für und k ≥ 2 ist tatsächlich eine stärkere Härte bekannt. Selbst wenn es tatsächlich eine Zuordnung von nur zwei Werten zu den Variablen gibt, die alle NAE-Bedingungen erfüllt (mit anderen Worten, der ℓ- einheitliche Hypergraph kann mit zwei Farben ohne monochromatische Hyperkante eingefärbt werden), ist es immer noch schwierig, eine zu finden Zuweisung von einer Domänengröße k, die mindestens 1 - 1 / k ℓ - 1 + ϵ NAE - Bedingungen erfüllt (für beliebige Konstante ϵ > $\ell \ge 4$$k \ge 2$$\ell$$k$$1-1/k^{\ell-1}+\epsilon$$\epsilon > 0$). Dies ergibt sich leicht aus der Tatsache, dass das bekannte Unangemessenheitsergebnis für die Hypergraph-2-Färbung eine starke Dichteangabe in Bezug auf die Solidität ergibt. Die formale Aussage erscheint in meinem SODA 2011-Artikel mit Ali Sinop "Die Komplexität, unabhängige Mengen in (Hyper-) Graphen mit begrenzten Graden und niedriger chromatischer Zahl zu finden" (Lemma 2.3 in der SODA-Endversion und Lemma 2.8 in der älteren Version, die auf ECCC verfügbar ist http://eccc.hpi-web.de/report/2010/111/ ).

Ich bin auf dieser Seite von einer Suche nach NAE-3SAT gelandet.

Ich bin mir ziemlich sicher, dass es für das von Ihnen gestellte Problem schwierig sein sollte , festzustellen, ob die Instanz erfüllbar ist oder ob höchstens Bruchteil der Bedingungen erfüllt werden können. Das heißt, ein enges Härteergebnis (das mit dem übereinstimmt, was durch einfaches Auswählen einer zufälligen Zuweisung erreicht werden würde) für befriedigende Fälle und ohne die UGC.$1-1/k^{\ell-1}+\epsilon$

Für und ℓ ≥ 4 folgt dies aus Hastads Faktor 7/8 + Epsilon-Unnäherungsergebnis für die 4-Mengen-Aufteilung (die dann für k > 4 auf die k-Mengen-Aufteilung reduziert werden kann ). Wenn die Negationen in Ordnung sind, kann man auch sein Ergebnis der engen Härte für Max ( ℓ - 1 ) -SAT verwenden.$k=2$$\ell \ge 4$$k > 4$$\ell-1$

Für hat Khot dies in einem FOCS 2002-Papier "Härte der Färbung von 3-färbbaren 3-einheitlichen Hypergraphen" bewiesen. (Das heißt, er hat die ursprüngliche UGC-Annahme entfernt.)$k=\ell=3$

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

Für den allgemeinen Fall weiß ich nicht, ob dies irgendwo niedergeschrieben wurde. Aber wenn Sie es wirklich brauchen, kann ich wahrscheinlich etwas finden oder die Behauptung überprüfen.

Prasad Raghavendra hat in seinem STOC'08 Best Paper unter der Annahme der Unique Games Conjecture bewiesen, dass ein einfacher semidefiniter Programmieralgorithmus die beste Näherung für jedes Problem der Bedingungserfüllung (einschließlich NAE) mit Einschränkungen für die konstante Anzahl von Variablen und mit konstantem Alphabet liefert. Um tatsächlich zu wissen, was der Härtefaktor für NAE ist, müssen Sie verstehen, wie gut der einfache Algorithmus dafür geeignet ist, dh, Sie müssen eine Integritätslücke für das Programm nachweisen. Ich weiß nicht, ob das jemand schon für NAE in seiner Gesamtheit getan hat oder nicht.