Czy występują luki w problemach z maksymalnym ograniczeniem?

Równoważna kompozycja PCF twierdzenie jest: max dla 3-SAT jest -hard odróżnić spe wzorów i wzorach w których co najwyżej r -fraction z klauzul spe (jakiegoś R < 1 ).$NP$$r$$r\lt 1$

Czy istnieje znane twierdzenie o dychotomii, które klasyfikuje wszystkie Max CSP na podstawie tego, czy mają one luki, czy nie?

Edytuj 16 grudnia 2010 : MAX CSP z twardą przerwą oznacza, że ​​problem ma optymalny współczynnik niedopuszczalności. Na przykład, 3SAT ma twardą lukę w jednym miejscu, ponieważ jest wielomian czas approximable do współczynnika , ale to jest N P -hard uzyskanie czynnika zbliżenia 7 / 8 + ε nawet gdy wszystkie klauzule są spełnialna.$7/8$$NP$$7/8+ \epsilon$

Prasad Raghavendra w najlepszej pracy STOC'08 udowodnił hipotezę dychotomii dla przybliżenia Max-CSP przy założeniu Unique Games Conjecture. Nie tak to pierwotnie przedstawił, ale kilka lat później wygłosił wykłady prezentujące różne rzeczy, np. W IAS, gdzie został nagrany na wideo: http://www.math.ias.edu/seminars/abstract ? event = 36669

Różnica w stosunku do pokazywania twardości SNP polega na tym, że mówimy tutaj o ilościowo optymalnych wynikach.

Twierdzenie 5.14 Khanna, Sudan, Trevisan i Williamson [KSTW01] podaje twierdzenie dychotomii dla wersji szczelinowych z doskonałą kompletnością dla problemów logicznych MaxCSP.

[KSTW01] Sanjeev Khanna, Madhu Sudan, Luca Trevisan i David P. Williamson. Przybliżalność stałych problemów satysfakcji. SIAM Journal on Computing , 30 (6): 1863–1920, 2001. http://dx.doi.org/10.1137/S0097539799349948

Jeśli się nie mylę, ostatecznym wynikiem na tym froncie jest Nadia Creignou, która pokazała, że każdy problem w MAX CSP można rozwiązać w czasie polytime lub jest on trudny w przypadku MAX SNP .