Tvrdost aproximace - Hardness of approximation

v počítačová věda, tvrdost aproximace je obor, který studuje algoritmická složitost hledání téměř optimálního řešení optimalizační problémy.

Rozsah

Tvrdost aproximace doplňuje studium aproximační algoritmy prokázáním limitu faktorů, s nimiž lze účinně aproximovat jejich řešení, u určitých problémů. Typicky takové limity ukazují faktor přiblížení, za kterým se problém stane NP-tvrdé, z čehož vyplývá, že zjištění a polynomiální čas aproximace problému není možná, pokud NP = P. Určitá tvrdost výsledků aproximace však vychází z jiných hypotéz, z nichž pozoruhodná je domněnky o jedinečných hrách.

Dějiny

Od začátku 70. let bylo známo, že mnoho optimalizačních problémů nelze vyřešit v polynomiálním čase, pokud P = NP, ale u mnoha z těchto problémů lze optimální řešení do určité míry efektivně přiblížit. V 70. letech Teofilo F. Gonzalez a Sartaj Sahni zahájil studium tvrdosti aproximace tím, že ukázal, že určité problémy s optimalizací byly NP-těžké dokonce i v rámci daného přibližný poměr. To znamená, že pro tyto problémy existuje prahová hodnota, aby bylo možné použít jakoukoli aproximaci polynomiálního času s aproximačním poměrem nad touto prahovou hodnotou k vyřešení NP-úplných problémů v polynomiálním čase.[1] Na počátku 90. let s rozvojem PCP Teorie vyšlo najevo, že je mnohem obtížnější aproximovat mnohem více aproximačních problémů a že (pokud P = NP) mnoho známých aproximačních algoritmů nedosahuje nejlepšího možného aproximačního poměru.

Tvrdost teorie aproximace se zabývá studiem prahové hodnoty aproximace těchto problémů.

Příklady

Příklad problému s NP-hard optimalizací, který je obtížné přiblížit, viz nastavit kryt.

Viz také

Reference

  1. ^ Sahni, Sartaj; Gonzalez, Teofilo (1976), "P-úplné problémy s aproximací ", Deník ACM, 23 (3): 555–565, doi:10.1145/321958.321975, hdl:10338.dmlcz / 103883, PAN  0408313.

Další čtení

externí odkazy