En informatique théorique, plus précisément en théorie de la complexité, P/poly est la classe de problèmes de décision décidés par une famille de circuits booléens de tailles polynomiales. Cette classe a été introduite par Karp et Lipton en 1980[1]. Cette classe est importante, car comme P est incluse dans P/poly, si on démontre que NP ⊈ P/poly, alors on résout le problème ouvert P est différent de NP[2].
- ↑ Richard M. Karp et Richard J. Lipton, « Some Connections Between Nonuniform and Uniform Complexity Classes », Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, ACM, sTOC '80, , p. 302–309 (ISBN 9780897910170, DOI 10.1145/800141.804678, lire en ligne, consulté le )
- ↑ (en) Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, (ISBN 0-521-42426-7), chap. 6 (« Boolean circuits »), p. 6.5