Twardość UGC predykatu

Tło :

W oryginalnym dokumencie UGC Subhash Khota ( PDF ) udowadnia trudność UG w podejmowaniu decyzji, czy dana instancja CSP z ograniczeniami w całej formie Niezupełna (a, b, c) w stosunku do trójskładnikowego alfabetu przyznaje zadanie spełniające 1 - ograniczeń lub czy nie ma zadowalających zadań $\epsilon$ograniczeń, dla dowolnie małychϵ>0.$\frac{8}{9}+\epsilon$$\epsilon > 0$

Jestem ciekaw, czy wynik ten został uogólniony dla dowolnej kombinacji -ary ograniczeń dla £ -l ≥ 3 i domen zmiennych wielkości k ≥ 3 , gdzie £ -l ≠ k ≠ 3 . To jest,$\ell$$\ell \ge 3$$k \ge 3$$\ell \ne k \ne 3$

Pytanie :

Czy znana jest twardość wyników aproksymacji dla predykatu dla x i ∈ G F ( k ) dla ℓ , k ≥ 3 i ℓ ≠ k ≠ 3 ? $NAE(x_1, \dots, x_\ell)$$x_i \in GF(k)$$\ell, k \ge 3$$\ell \ne k \ne 3$

Szczególnie interesuje mnie kombinacja wartości ; np. predykat Nie równe ( x 1 , … , x k ) dla x 1 … , x k ∈ G F ( k ) .$\ell = k$$x_1, \dots, x_k$$x_1 \dots, x_k \in GF(k)$

Zrozumiałem, że to, co twierdziłem powyżej, jest w rzeczywistości znane.

Dla i arbitralnego k ≥ 3 , jest to w pracy Khota FOCS 2002 „Twardość zabarwienia 3-kolorowych 3-jednolitych hipergraphów” (praca faktycznie mówi o ogólnym$\ell = 3$$k \ge 3$ , chociaż tytuł mówi tylko o 3-kolorowym przypadku) .$k$

Dla i k ≥ 2 , w rzeczywistości znana jest większa twardość. Nawet jeśli w rzeczywistości jest przypisanie wartości do zaledwie dwóch zmiennych, które spełnia wszystkie warunki NAE (innymi słowy ℓ hipergraf -uniform mogą być barwione przy użyciu 2 kolory bez monochromatycznego hyperedge), nadal jest NP-trudne do znalezienia przypisanie z rozmiaru domeny k, który spełnia co najmniej 1 - 1 / k ℓ - 1 + ϵ ograniczenia NAE (dla arbitralnej stałej$\ell \ge 4$$k \ge 2$$\ell$$k$$1-1/k^{\ell-1}+\epsilon$$\epsilon > 0$). Wynika to łatwo z faktu, że znany wynik niedoceniania dla barwienia metodą hypergraph 2 daje mocne stwierdzenie gęstości w przypadku dźwięku. Formalne oświadczenie pojawia się w moim artykule SODA 2011 z Ali Sinopem „Złożoność znalezienia niezależnych zbiorów w grafach o ograniczonym stopniu (hiper) niskiej liczby chromatycznej” (Lemma 2.3 w ostatecznej wersji SODA i Lemma 2.8 w starszej wersji dostępnej na ECCC http://eccc.hpi-web.de/report/2010/111/ ).

Wylądowałem na tej stronie z wyszukiwania dotyczącego NAE-3SAT.

Jestem pewien, że za problem prosicie, powinno być NP-ciężko powiedzieć, czy instancja jest spe, czy co najwyżej ułamek ograniczeń mogą być spełnione. Oznacza to ścisły wynik twardości (dopasowanie do tego, co osiągnęłoby po prostu losowe przypisanie), dla zadowalających przypadków i bez potrzeby korzystania z UGC.$1-1/k^{\ell-1}+\epsilon$

$k=2$$\ell \ge 4$$k > 4$$\ell-1$

$k=\ell=3$

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

W ogólnym przypadku nie wiem, czy to gdziekolwiek zostało zapisane. Ale jeśli naprawdę tego potrzebujesz, prawdopodobnie mogę coś znaleźć lub sprawdzić roszczenie.

Prasad Raghavendra w swoim STOC'08 Best Paper udowodnił, przy założeniu Unique Games Conjecture, że prosty algorytm programowania półfinałowego daje najlepsze przybliżenie dla każdego problemu satysfakcji z ograniczeń (w tym NAE) z ograniczeniami dla stałej liczby zmiennych i stałym alfabetem. Aby faktycznie wiedzieć, jaki jest współczynnik twardości dla NAE, musisz zrozumieć, jak dobrze radzi sobie z tym prosty algorytm, tj. Udowodnić lukę w integralności programu. Nie wiem, czy ktoś już to zrobił dla NAE w swojej pełnej ogólności, czy nie.