Complexitat de circuits

La complexitat de circuits és una branca de la teoria de la complexitat en la que les funcions booleanes es classifiquen segons la mida o profunditat del circuit booleà que la computa. Es pot parlar, per tant, de la complexitat d'un circuit booleà. També hi ha el concepte associat de la complexitat d'un circuit d'un llenguatge recursiu que és decidible per una família uniforme de circuits $C_{1},C_{2},\ldots$

Les classes de complexitat definides en termes de circuits booleans són les classes AC⁰, AC, TC⁰ i NC.

Mida i profunditat

Un circuit booleà amb n bits d'entrada és un graf acíclic dirigit on cada node (dites portes en aquest context) és un node d'entrada etiquetat com un dels n bits, o bé una porta AND, OR o NOT. Una d'aquestes portes es designa com la porta de sortida. Un circuit d'aquest tipus computa una funció dels seus n bits d'entrada. La mida del circuit és el nombre de portes que conté i la seva profunditat és la mida del camí més llarg entre una porta d'entrada i la porta de sortida.

Hi ha dos conceptes principals en complexitat de circuits: la mida de circuit d'una funció booleana $f$ és la mida mínima de qualsevol circuit computant $f$. La profunditat de circuit d'una funció boolena $f$ és la profunditat mínima de qualsevol circuit que computa $f$.

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 $C_{1},C_{2},\ldots$on cada $C_{n}$accepta una entrada de mida n. Cada família de circuits genera el llenguatge $C_{n}$, 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 $C_{n}$(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 $A$ es defineix com la funció $t:{\mathbb {N} }\to {\mathbb {N} }$que relaciona la longitud d'entrada n a la mida del circuit mínim $C_{n}$capaç de decidir si una entrada de dita longitud està a $A$.

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à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 $C_{1},C_{2},\ldots$on cada $C_{n}$é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 $C_{n}$. Quan aquesta màquina de Turing té un 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⁰ o TC⁰. 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.

Uniforme en temps polinòmic

Una família de circuits booleans $\{C_{n}:n\in {\mathbb {N} }\}$és de temps polinòmic si existeix una màquina de Turing determinista M, tal que:

• M funciona en temps polinòmic
• per tot $n\in \mathbb {N}$, M treu una descripció de $C_{n}$en entrada 1ⁿ

Uniforme en logspai

Una família de circuits booleans $\{C_{n}:n\in {\mathbb {N} }\}$és d'espai logarítmic si existeix una màquina de Turing determinista M, tal que:

• M funciona en espai logarítmic
• per tot $n\in \mathbb {N}$, M treu una descripció de $C_{n}$en entrada 1ⁿ

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^i, consistent en circuits de mida polinòmica de profunditat $O(\log ^{i}(n))$utilitzant portes AND, OR i NOT limitades en el seu fan-in.

La classe uniforme TC⁰ està estrictament continguda dins de PP.

Les classes de complexitat SP
2, PP i MA/1 no estan dins de MIDA(n^k) per qualsevol constant k.

Se sap que NEXP $\not \subseteq$ACC⁰.

No se sap si NEXPTIME conté TC⁰.

Vegeu també

• Circuit booleà
• Classe de complexitat NC
• Classe de complexitat AC