Els grafs de configuració són una eina teòrica que s'utilitza en la teoria de la complexitat computacional per demostrar una relació entre l'accessibilitat dels grafs i les classes de complexitat.
Definició Un model computacional teòric, com la màquina de Turing o els autòmats finits, explica com fer un càlcul. El model explica tant què és una configuració inicial de la màquina com quins passos es poden seguir per continuar el càlcul, fins que finalment s'atura. Una configuració, també anomenada descripció instantània (ID), és una representació finita de la màquina en un moment determinat. Per exemple, per a un autòmat finit i una entrada determinada, la configuració serà l'estat actual i el nombre de lletres llegides, per a una màquina de Turing serà l'estat, el contingut de la cinta i la posició del capçal.
Un graf de configuració és un graf etiquetat dirigit on l'etiqueta dels vèrtexs són les configuracions possibles dels models i on hi ha una vora d'una configuració a una altra si correspon a un pas computacional del model.
Les configuracions inicial i d'acceptació de la màquina són vèrtexs especials del graf de configuració. El càlcul accepta si i només si hi ha un camí des d'un vèrtex inicial a un vèrtex acceptant.
Propietat útil Si existeix exactament un estat inicial, aleshores un càlcul és determinista si i només si des de qualsevol configuració hi ha com a màxim un pas possible, de manera que si i només si el graf és de grau superior a . S'afegeix un vèrtex d'acceptació fictici amb una aresta de cada vèrtex d'acceptació, per comprovar si hi ha un càlcul d'acceptació, només cal comprovar si hi ha un camí des del vèrtex inicial al vèrtex d'acceptació, que és el problema d'accessibilitat.
Es diu que un càlcul és inequívoc si existeix com a màxim un camí des d'un vèrtex inicial fins a un vèrtex acceptant.
Un cicle al graf correspon a un bucle infinit en el càlcul.
Mida del graf El graf computacional pot tenir una mida infinita si no hi ha restriccions sobre les possibles configuracions; de fet, és fàcil veure que hi ha màquines de Turing que poden assolir configuracions arbitràriament grans.
També és possible tenir grafs finits: a l'autòmat finit determinista amb estats, per a una paraula donada de mida la configuració està composta per la posició del cap i l'estat actual. Per tant, el graf és de mida , i la part accessible des de l'estat inicial és de mida , de manera que el graf de configuració és de la mida .
Usos Aquesta noció és útil perquè redueix els problemes computacionals a problemes d'accessibilitat del graf. En la mida de l'entrada, i com que la configuració d'una màquina de Turing a NL és efectivament de mida logarítmica, es dedueix que l'accessibilitat del graf és completa per a NL.Papadimitriou, Christos H. (1994). Computational Complexity, Reading, Massachusetts: Addison-Wesley. .
En l'altra direcció, ajuda a verificar la complexitat d'un model de càlcul; el problema de decisió per a un model (determinista) les configuracions del qual són d'espai que és logarítmica en la mida de l'entrada està en (L) NL. Aquest és per exemple el cas dels autòmats finits i els autòmats finits amb un comptador.
Referències
Categoria:Teoria de grafs