APX (complexité)
classe de complexité
En théorie de la complexité, APX est la classe des problèmes algorithmiques pour lesquels il existe un algorithme d'approximation en temps polynomial avec un ratio d'approximation constant[1].
Cette classe est égale à la classe MaxSNP si l'on considère certains types de réductions[1]. Elle contient la classe PTAS, des problèmes qui admettent un schéma d'approximation en temps polynomial.
Le problème d'optimisation Vertex Cover appartient par exemple à cette classe (et est complet pour certaines réductions), par contre, le problème de la clique maximum n'appartient pas à cette classe sauf si P = NP.
Notes et références
🔥 Top keywords: Wikipédia:Accueil principalListe de sondages sur les élections législatives françaises de 2024Spécial:RechercheJordan BardellaChampionnat d'Europe de football 2024N'Golo KantéJodie DevosKylian MbappéÉlections législatives françaises de 2024Marcus ThuramLe Jardin des Finzi-Contini (film)Maria Schneider (actrice)Cookie (informatique)Championnat d'Europe de footballNouveau Front populaireKevin DansoAntoine GriezmannÉric CiottiChampionnat d'Europe de football 2020Dominique SandaMike MaignanWilliam SalibaLionel JospinÉlections législatives de 2024 dans l'EssonneFront populaire (France)Françoise HardyÉlections législatives de 2024 à ParisRassemblement nationalJean-Luc MélenchonFichier:Cleopatra poster.jpgOlivier GiroudSébastien ChenuDidier DeschampsLa Chronique des BridgertonÉlections législatives de 2024 dans les YvelinesLilian ThuramListe de partis politiques en FranceAnne SinclairGabriel Attal