risultato Inapproximability implica APX-durezza?

Question

Se un problema di ottimizzazione è noto per essere fino inapproximable a una certa precisione, ciò implica automaticamente che il problema è APX-hard?

Answer 1

Se P $ = $ NP poi c'è un algoritmo polytime per qualsiasi problema di ottimizzazione NP, e così tutti problema è APX-hard. Quindi, da ora in poi, si supponga che P $ \ neq $ NP.

Si può associare a qualsiasi problema decisionale $ L \ in NP $ un problema di ottimizzazione $ o_L $ definendo $ o_L (x) = 1 $ se $ x \ in L $ e $ o_L (x) = 2 $ in caso contrario. Supponiamo $ o_L $ riduce a $ o_M $ tramite una riduzione PTAS $ (f, g, \ alpha) $ (notazione come nel Wikipedia articolo ). Sia $ C = 1+ \ alpha (1/2) $. Così se $ y $ un $ C $ -approximation a $ o_M (f (x)) $ allora $ g (x, y, 1/2) $ è una (x) $ $ 3/2 $ -approximation a $ o_L , da cui possiamo determinare se $ x \ in L $ o meno. Complessivamente, questo dà una riduzione polytime da $ L $ a $ M $. Ora prendete qualsiasi linguaggio NP-completo per $ L $ e qualsiasi linguaggio NP-intermedio per $ M $ (esiste un tale linguaggio a causa del teorema di Ladner). Da un lato, dal momento che $ M \ notin P $, è possibile $ non 2-approssimativa o_M $. D'altra parte, $ L $ non riduce a $ M $ (dato che si applicherebbe che $ M $ è NP-completo), e così $ o_L $ non riduce a $ o_M $. Concludiamo che $ o_M $ è non APX-hard.