P/poly
Sign in to saveIn computational complexity theory, P/poly is a complexity class that can be defined in both circuit complexity and non-uniform complexity. Since the two definitions are equivalent, this concept bridges the two areas.
~8 min read
Article
5 sectionsContents
- Formal definition
- Importance of P/poly
- Bounded-error probabilistic polynomial is contained in P/poly
- Proof
- References
In computational complexity theory, P/poly is a complexity class that can be defined in both circuit complexity and non-uniform complexity. Since the two definitions are equivalent, this concept bridges the two areas.
In the perspective of circuit complexity, P/poly is the class of problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families.
Connections
BPP
Entity
♯P
Entity
International Standard Book Number
Entity
cryptography
Entity
digital object identifier
Entity
Turing machine
Entity
Q118398
Entity
formal language
Entity
Cambridge University Press
Entity
open access
Entity
computational complexity theory
Entity
Leonard Adleman
Entity
Avi Wigderson
Entity
NP
Entity
NP-complete
Entity
decision problem
Entity
P
Entity
regular language
Entity
NP-hard
Entity
complexity class
Entity