Complexitat de circuits: diferència entre les revisions
Contingut suprimit Contingut afegit
m neteja i estandardització de codi |
m neteja i estandardització de codi |
||
Línia 8:
Hi ha dos conceptes principals en complexitat de circuits: la mida de circuit d'una funció booleana <math>f</math> és la mida mínima de qualsevol circuit computant <math>f</math>. La profunditat de circuit d'una funció boolena <math>f</math> és la profunditat mínima de qualsevol circuit que computa <math>f</math>.
Aquests conceptes es generalitzen quan es considera la complexitat de circuits d'un llenguatge que conté cadenes amb diferents longituds d'entrada, especialment llenguatges formals infinits. Els circuits booleans només permeten un valor fix de bits d'entrada, per tant cap circuit booleà pot decidir sobre un llenguatge d'aquest tipus. Per poder treballar amb ells, es consideren families de circuits <math>C_{{1}},C_{{2}},\ldots </math>on cada <math> C_{n}</math>accepta una entrada de mida ''n''. Cada família de circuits genera el llenguatge <math> C_{n}</math>, treien com a sortida un 1 quan una cadena de mida ''n'' és membre de la família o 0 si no ho és. Es diu que una família de circuits és mínima si no hi ha cap altra família que decideixi sobre la mida d'entrada ''n'' amb un circuit més petit que <math> C_{n}</math>(es fa de forma equivalent per famílies de profunditat mínima). Per tot això, té sentit parlar de complexitat de circuits inclús per llenguatges no recursius.
Per tant, la complexitat d'un [[llenguatge formal]] <math>A</math> es defineix com la funció <math> t:{\mathbb {N}}\to {\mathbb {N}}</math>que relaciona la longitud d'entrada ''n'' a la mida del circuit mínim <math> C_{n}</math>capaç de decidir si una entrada de dita longitud està a <math>A</math>.
== Uniformitat ==
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 té un [[Temps polinòmic|temps d'execució polinòmic]] en ''n'', el circuit es diu que és P-uniforme.
El requeriment més estricte [[DLOGTIME]]-uniforme és de particular interès per estudiar les classes de complexitat AC<sup>0</sup> o TC<sup>0</sup>. Quan no s'especifica cap restricció, un llenguatge és recursiu (decidible per una màquina de Turing) [[si i només si]] el llenguatge és decidible per una família uniforme de circuits booleans.
Línia 30:
== Classes de complexitat ==
Força classes de complexitat es defineixen en termes de complexitat de circuits. Per cada enter no negatiu ''i'', hi ha una classe NC<sup>i,</sup> consistent en circuits de mida polinòmica de profunditat <math>O(\log ^{i}(n))</math>utilitzant portes AND, OR i NOT limitades en el seu fan-in.
La classe uniforme TC<sup>0</sup> està estrictament continguda dins de PP.<ref>{{Ref-publicació|cognom=Allender|nom=Eric|article=Circuit complexity before the dawn of the new millennium|publicació=Technical Report|llengua=en|url=https://link.springer.com/chapter/10.1007/3-540-62034-6_33|data=1996-12-18|editorial=Springer, Berlin, Heidelberg|pàgines=1–18|doi=10.1007/3-540-62034-6_33}}</ref>
| |||