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ć?
źródło
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ść.
źródło
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
źródło
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.).
źródło