Twardość aproksymacji bez twierdzenia PCP

36

Ważnym zastosowaniem twierdzenia PCP jest to, że daje wyniki typu „twardość aproksymacji”. W niektórych stosunkowo prostszych przypadkach można udowodnić taką twardość bez PCP. Czy jest jednak jakikolwiek przypadek, w którym twardość wyniku aproksymacji została najpierw udowodniona przy użyciu twierdzenia PCP, tj. Wynik nie był wcześniej znany, ale później znaleziono bardziej bezpośredni dowód, który nie zależy od PCP? Innymi słowy, czy jest jakiś przypadek, w którym PCP wydawało się konieczne najpierw, ale później można je wyeliminować?

cc.complexity-theory approximation-hardness pcp

— Andras Farago
źródło

35

Przykładem jest ten artykuł:

Guruswami, V., i Khanna, S. (2004). Na twardości 4-kolorowania 3-kolorowy graf. SIAM Journal on Discrete Mathematics , 18 (1): 30–40. połączyć

Korzystając z twierdzenia PCP, Khanna, Linial i Safra (2000) udowodnili, że trudno jest kolorować trójkolorowy graf przy użyciu zaledwie 4 kolorów. Później Guruswami i Khanna (2004) dali między innymi niezawodny dowód na ten sam wynik bez PCP.

— vb le
źródło

11

Czy zechciałbyś opisać artykuł w swojej odpowiedzi, zamiast wskazywać na niego hiperłączem?

— Niel de Beaudrap,

15

Dla problemu maksymalnych ścieżek rozłącznych krawędzi w grafach ukierunkowanych papier Ma & Wanga (2000) został oparty na problemie pokrycia etykiety, który z kolei jest oparty na twierdzeniu PCP. Następnie Guruswami i in. Stwierdzili prostą redukcję za pomocą twardości problemu 2-rozłącznego . glin. (2003), co również poprawiło twardość.

— Chandra Chekuri
źródło

Ale czy twardość 2-rozłączna ścieżki wymaga PCP?

— Suresh Venkat,

3

@SureshVenkat, 2-disjointpaths nie wymaga PCP. Problem polega na tym, czy na kierunkowym wykresie istnieją rozłączne ścieżki łączące i . Wykazano, że jest to NP-Complete poprzez skomplikowaną redukcję gadżetów od SAT, autorstwa Fortune, Hopcroft i Wylie.

(s_{1}, t_{1})

$(s_1,t_1)$

(s_{2}, t_{2})

$(s_2,t_2)$

G

$G$

— Chandra Chekuri,

13

Istnieją przykłady z przybliżonego liczenia. W przybliżeniu policzenie liczby spełniających przypisanie relacji NP może być trudniejsze niż rozstrzygnięcie, czy zadowalające przypisanie istnieje, więc nie jest zaskakujące, że nie trzeba twierdzenia PCP, aby udowodnić twardość dla takich problemów. Mimo to twierdzenie PCP czasami stanowi dogodny punkt wyjścia, np. W tym artykule o przybliżeniu liczby niezależnych zbiorów na rzadkim wykresie: http://www.dcs.ed.ac.uk/home/mrj/papers/ DFJ02.pdf Później Sly udowodnił wynik twardości w przybliżeniu zliczając niezależne zestawy oparte na standardowej twardości NP Max-Cut: http://arxiv.org/pdf/1005.5584v1.pdf

— Dana Moshkovitz
źródło

1

d = 6

$d=6$

2

@DanielApon: późniejszy wynik zastosował niedopuszczalność MAX-CUT, aby dać jeszcze silniejszy wynik niedopuszczalności: arxiv.org/abs/1203.2602 pokazuje, że dla niektórych trudno jest w przybliżeniu zliczyć niezależne zestawy w 6-regularnych wykresach w stosunku proporcji . Nie sądzę, by optymalna wartość została zbadana, pod UGC lub w inny sposób.

c

$c$

e^{c n}

$e^{cn}$

c

$c$

— Colin McQuillan,

10

Inną odpowiedzią, która jest nieco odmienna od poprzednich odpowiedzi, jest praca Uri Feige: Relacje między średnią złożonością przypadku a złożonością przybliżenia .

Uri pokazuje, że przeciętne założenia przypadku mogą zastąpić twierdzenie PCP o udowodnieniu twardości przybliżenia niektórych problemów. Należy jednak pamiętać, że nie wiemy, jak udowodnić założenia dotyczące średnich przypadków i mamy pewne dowody, że nie będziemy w stanie udowodnić ich w oparciu o standardowe założenia dotyczące twardości NP (patrz artykuły Feigenbaum-Fortnow, Bogdanov-Trevisan itp.).

— Dana Moshkovitz
źródło