P
Peu commune
P/poly
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. Cette classe est importante, car comme P est incluse dans P/poly, si on démontre que N…
Extrait raccourci de l'article Wikipédia, CC BY-SA 4.0.