Complexitat de circuits: diferència entre les revisions

Els circuits booleans son dels primers exemples de models de computació no uniformes en el sentit que entrades de diferents longituds es processen per diferents circuits, en contrast amb els models uniformes com les [[Màquina de Turing|màquines de Turing]] on el mateix dispositiu computador processa totes les mides d'entrada. Un problema computacional individual s'associa amb una família particular de circuits booleans <math>C_{{1}},C_{{2}},\ldots </math>on cada <math> C_{n}</math>és el circuit encarregat de processar l'entrada de ''n'' bits. Sovint s'imposa una condició d'uniformitat a aquestes famílies, requerint l'existència d'una màquina de Turing fitada en recursos de computació de manera que, per una entrada ''n'', produeix una descripció del circuit individual <math> C_{n}</math>. Quan aquesta màquina de Turing teté un [[Temps polinòmic|temps d'execució polinòmic]] en ''n'', el circuit es diu que és P-uniforme.