Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Low (complexity)
Résumé
In computational complexity theory, a language B (or a complexity class B) is said to be low for a complexity class A (with some reasonable relativized version of A) if AB = A; that is, A with an oracle for B is equal to A.
Such a statement implies that an abstract machine which solves problems in A achieves no additional power if it is given the ability to solve problems in B at unit cost. In particular, this means that if B is low for A then B is contained in A. Informally, lowness means that problems in B are not only solvable by machines which can solve problems in A, but are “easy to solve”. An A machine can simulate many oracle queries to B without exceeding its resource bounds.
Results and relationships that establish one class as low for another are often called lowness results. The set of languages low for a complexity class A is denoted Low(A).
Several natural complexity classes are known to be low for themselves. Such a class is sometimes called self-low. Scott Aaronson calls such a class a physical complexity class. Note that being self-low is a stronger condition than being closed under complement. Informally, a class being low for itself means a problem can use other problems in the class as unit-cost subroutines without exceeding the power of the complexity class.
The following classes are known to be self-low:
P is self-low (that is, PP = P) because polynomial-time algorithms are closed under composition: a polynomial-time algorithm can make polynomially many queries to other polynomial-time algorithms, while retaining a polynomial running time.
PSPACE (with restricted oracle access mechanism) is also self-low, and this can be established by exactly the same argument.
L is self-low because it can simulate log space oracle queries in log space, reusing the same space for each query.
NC is also self-low for the same reason.
ZPP is also low for itself and the same arguments almost work for BPP, but one has to account for errors, making it slightly harder to show that BPP is low for itself.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.