UP (complexité)

Pour les articles homonymes, voir UP.

Cet article est une ébauche concernant l’informatique théorique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En théorie de la complexité, UP (en anglais : unambigous non-deterministic polynomial time) est la classe de complexité des problèmes de décision décidés par une machine de Turing non ambigüe (machine de Turing non-déterministe avec au plus une seule exécution acceptante pour une entrée donnée). Cette classe a été défini en 1976 par Valiant^[1].

Lien externe

(en) La classe UP sur le Complexity Zoo

Notes et références

↑ Leslie G. Valiant, « Relative complexity of checking and evaluating », Information Processing Letters, vol. 5, n^o 1,‎ 1^er mai 1976, p. 20–23 (ISSN 0020-0190, DOI 10.1016/0020-0190(76)90097-1, lire en ligne, consulté le 14 juillet 2019)

v · m

Théorie de la complexité (informatique théorique)

Classes de complexité
(liste)

Classes classiques	L NL P NP NP-complet co-NP co-NP-complet NP-facile PSPACE E EXPTIME NE NEXPTIME EXPSPACE
Classes randomisées et quantiques	RP ZPP BPP EQP BQP QMA IP Protocole Arthur-Merlin PP BPL RL
Autres	P/poly NC APX AC⁰ UP
Classes de fonctions calculables	#-P #-P-complet
Hiérarchies	Hiérarchie polynomiale PH Hiérarchie booléenne
Familles de classes	DTIME NTIME DSPACE NSPACE

Théorèmes et outils

Théorèmes structurels	Théorème de Savitch Théorème d'Immerman-Szelepcsényi Théorème PCP Théorème de Karp-Lipton Théorème de Sipser-Gács-Lautemann Théorème de Toda
Outils et réductions	Théorème d'accélération linéaire Théorème de Cook Réduction polynomiale Kernelisation

Approches non-standard

Portail de l'informatique théorique