Twardość UGC predykatu


16

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ń 8ϵograniczeń, dla dowolnie małychϵ>0.89+ϵϵ>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,3k3k3

Pytanie :

Czy znana jest twardość wyników aproksymacji dla predykatu dla x iG F ( k ) dla , k 3 i k 3 ? NAE(x1,,x)xiGF(k),k3k3

Szczególnie interesuje mnie kombinacja wartości ; np. predykat Nie równe ( x 1 , , x k ) dla x 1, x kG F ( k ) .=kx1,,xkx1,xkGF(k)


Proszę podać odniesienie dla przypadku ? k=3
Mohammad Al-Turkistany

@turkistany, po dokładniejszym przyjrzeniu się mojemu pytaniu, postanowiłem usunąć to pytanie częściowe (ponieważ jednocześnie zadawałem o wiele za dużo!). W pracy byłem pierwotnie powołując się, choć było to .
Daniel Apon

2
Jeśli opublikujesz pytanie dotyczące pracy Bułatowa, zauważ, że w ostatnim dziesięcioleciu nastąpiło znaczne uproszczenie tego podejścia. Kilka algorytmów zostało uproszczonych i połączonych. Zobacz ostatni artykuł LICS autorstwa Barto i Kozika.
András Salamon

1
@Andras: Zakładam, że masz na myśli to ? Wygląda interesująco; Na pewno to przeczytam, dzięki! W każdym razie prawdopodobnie wkrótce ponownie zadam poprzednie pytanie cząstkowe jako nowe pytanie, zakładając, że nie odpowiem na to samo (a ponadto brakuje mi czasu, aby upewnić się, że w tej chwili go poprawnie stwierdzę) .
Daniel Apon

tak, to jest to. Odniesienia w nim zapewniają szybką przegląd następnej historii.
András Salamon

Odpowiedzi:


9

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=3k3 , 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łej4k2k11/k1+ϵϵ>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/ ).


To całkiem piękne. Prawdopodobnie skończę z tym w najbliższej przyszłości. Dziękuję Ci!
Daniel Apon

14

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.11/k1+ϵ

k=24k>41

k==3

=3k3xi+a,xj+b,xka,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.


Dzięki za świetną odpowiedź! Nie byłem świadomy ostatniego artykułu, który połączyłeś (twojego z Engebretsen), i to na pewno pomoże. Nadal jestem zainteresowany ogólną sprawą (i spotkałem się z podobną sytuacją: nigdzie nie jest napisana!). Nawet coś dla=4 i arbitralne kprzypadek prawdopodobnie zapewni wystarczającą wiedzę.
Daniel Apon,

12

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.


O Boże! Przeczytałem też kilka innych wersji STOC Raghavendry. Powinienem był nawiązać to połączenie! Nie wiem też, czy wartości NAE zostały specjalnie obliczone, ale na pewno mnie zainteresują!
Daniel Apon
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.