Inom datavetenskap är approximationskomplexitet ett studieområde av beräkningskomplexiteten för att hitta lösningar på optimeringsproblem som är nära optimala.
Komplexiteten i approximation kompletterar studiet av approximationsalgoritmer genom att bevisa, för vissa problem, begränsningar för de parametrar med vilka problemlösningar effektivt kan approximeras. Typiskt visar sådana begränsningar orsakerna till att ett problem blir NP-hårt , under antagandet att en polynom- tidsapproximation till problemet inte är möjlig, om inte NP=P . Vissa resultat om svårigheten att approximera är dock baserade på andra hypoteser, av vilka gissningarna om spel med ett enda svar [1] [2] [3] är särskilt anmärkningsvärda .
Det har varit känt sedan tidigt 1970-tal att många optimeringsproblem inte kan lösas i polynomtid om inte NP=P , men i många sådana problem kan den optimala lösningen approximeras effektivt i någon grad. I början av 1990-talet, när teorin om PCP utvecklades , blev det klart att det finns gränser för graden av approximation av många optimeringsproblem - för många problem finns det en tröskel bortom vilken approximationen blir NP-hård . Approximationskomplexitetsteorin studerar sådana approximationströsklar.
Ett exempel på ett NP-hårt optimeringsproblem som är svårt att approximera är uppsättningstäckningsproblemet [4] .