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 [1]

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

Mida i profunditatModifica

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   és la mida mínima de qualsevol circuit computant  . La profunditat de circuit d'una funció boolena   és la profunditat mínima de qualsevol circuit que computa  .

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  on cada  accepta una entrada de mida n. Cada família de circuits genera el llenguatge  , 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  (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   es defineix com la funció  que relaciona la longitud d'entrada n a la mida del circuit mínim  capaç de decidir si una entrada de dita longitud està a  .

UniformitatModifica

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  on cada  é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  . 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 AC0 o TC0. 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òmicModifica

Una família de circuits booleans  és de temps polinòmic si existeix una màquina de Turing determinista M, tal que:

  • M funciona en temps polinòmic
  • per tot  , M treu una descripció de  en entrada 1n

Uniforme en logspaiModifica

Una família de circuits booleans  és d'espai logarítmic si existeix una màquina de Turing determinista M, tal que:

  • M funciona en espai logarítmic
  • per tot  , M treu una descripció de  en entrada 1n

Classes de complexitatModifica

Força classes de complexitat es defineixen en termes de complexitat de circuits. Per cada enter no negatiu i, hi ha una classe NCi, consistent en circuits de mida polinòmica de profunditat  utilitzant portes AND, OR i NOT limitades en el seu fan-in.

La classe uniforme TC0 està estrictament continguda dins de PP.[2]

Les classes de complexitat SP
2
, PP i MA/1 no estan dins de MIDA(nk) per qualsevol constant k.[3][4]

Se sap que NEXP  ACC0.[5]

No se sap si NEXPTIME conté TC0.

Vegeu tambéModifica

ReferènciesModifica

  1. Michael., Sipser,. Introduction to the theory of computation. 3rd ed. Boston, MA: Cengage Learning, 2013. ISBN 9781133187790. 
  2. Allender, Eric «Circuit complexity before the dawn of the new millennium» (en anglès). Technical Report. Springer, Berlin, Heidelberg, 18-12-1996, pàg. 1–18. DOI: 10.1007/3-540-62034-6_33.
  3. «A note on the circuit complexity of PP» (en anglès). Theoretical Computer Science, 347, 1-2, 30-11-2005, pàg. 415–418. DOI: 10.1016/j.tcs.2005.07.032. ISSN: 0304-3975.
  4. Santhanam, Rahul «Circuit Lower Bounds for Merlin-Arthur Classes». STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. ACM [Nova York, NY, USA], 2007, pàg. 275–283. DOI: 10.1145/1250790.1250832.
  5. Williams, R. «Non-uniform ACC Circuit Lower Bounds». Proceedings of the 26th Annual IEEE Conference on Computational Complexity, 2011-6, pàg. 115–125. DOI: 10.1109/CCC.2011.36.