Inden for datalogi er tilnærmelseskompleksitet et studiefelt af den beregningsmæssige kompleksitet ved at finde løsninger på optimeringsproblemer, der er tæt på optimale.
Kompleksiteten af tilnærmelse supplerer studiet af tilnærmelsesalgoritmer ved at bevise, for nogle problemer, begrænsninger på de parametre, hvormed problemløsninger effektivt kan tilnærmes. Typisk viser sådanne begrænsninger årsagerne til, at et problem bliver NP-hårdt , under den antagelse, at en polynomiel- tidstilnærmelse til problemet ikke er mulig, medmindre NP=P . Nogle resultater om sværhedsgraden ved tilnærmelse er dog baseret på andre hypoteser, hvoraf formodningen om spil med et enkelt svar [1] [2] [3] er særligt bemærkelsesværdig .
Det har været kendt siden begyndelsen af 1970'erne, at mange optimeringsproblemer ikke kan løses i polynomiel tid, medmindre NP=P , men i mange sådanne problemer kan den optimale løsning tilnærmes effektivt til en vis grad. I begyndelsen af 1990'erne, efterhånden som teorien om PCP udviklede sig , blev det klart, at der er grænser for graden af tilnærmelse af mange optimeringsproblemer - for mange problemer er der en tærskel, ud over hvilken tilnærmelsen bliver NP-hård . Tilnærmelseskompleksitetsteori studerer sådanne tilnærmelsestærskler.
Et eksempel på et NP-hårdt optimeringsproblem, som er svært at tilnærme sig, er det sæt dækkende problem [4] .