V informatice je složitost přiblížení oborem výpočetní složitosti hledání řešení optimalizačních problémů , které jsou blízké optimálnímu.
Složitost aproximace doplňuje studium aproximačních algoritmů tím, že pro některé problémy dokazuje omezení parametrů, kterými lze efektivně aproximovat řešení problémů. Obvykle taková omezení ukazují důvody, proč se problém stává NP-těžkým , za předpokladu, že polynomiální časová aproximace problému není možná, ledaže NP=P . Některé výsledky o obtížnosti aproximace jsou však založeny na jiných hypotézách, z nichž za pozornost stojí zejména domněnka o hrách s jedinou odpovědí [1] [2] [3] .
Od počátku 70. let je známo, že mnoho optimalizačních problémů nelze vyřešit v polynomiálním čase, pokud není NP=P , ale u mnoha takových problémů lze optimální řešení do určité míry efektivně aproximovat. Na počátku 90. let, jak se teorie PCP vyvíjela , se ukázalo, že existují limity pro míru aproximace mnoha optimalizačních problémů - pro mnoho problémů existuje práh, za kterým se aproximace stává NP-těžkou . Teorie aproximační složitosti studuje takové aproximační prahy.
Příkladem NP-tvrdého optimalizačního problému, který je obtížné aproximovat, je problém pokrytí množin [4] .