Configuração de grafos

Configuração de grafos é uma ferramenta teórica usada na teoria da complexidade computacional para provar a relação entre o problema de alcance dos grafos e a complexidade de classes.

Definição

Um modelo teórico computacional, como uma máquina de Turing ou autômato finito, explica como executar um processo de computação. Os modelos explicam o que significa uma configuração inicial da máquina e quais passos podem ser dados para continuar a computação, até que eventualmente pare. Uma configuração, também chamada de descrição instantânea (ID) é uma representação finita da máquina em um determinado tempo. Por exemplo, para um autômato finito, dado uma entrada, a configuração será o estado atual e o numero de letras lidas, para uma máquina de Turing será o estado, o conteúdo da fita e a posição da cabeça da leitora. Um grafo de configuração é um grafo dirigido rotulado onde o rótulo dos vértices são as configurações possíveis dos modelos e onde existe uma aresta de uma configuração para outra se corresponder a um passo computacional do modelo.

A configuração de aceitação e inicial da máquina são vértices especiais do grafo de configuração. A computação aceita se e somente se existe um caminho de um vértice inicial para um vértice de aceitação.

Propriedades úteis

Se a computação é determinística, então para qualquer computação, existe no máximo, um passo possível, de modo que o grafo é de grau um, e existe um estado inicial. Uma vez que adicionamos um vértice inicial falso com uma aresta conectando para todos os outros vértices iniciais e um vértice de aceitação falso com uma aresta conectando para todos os outros vértices de aceitação, checando se existe uma computação de aceitação só será necessário verificar se existe um caminho do vértice inicial para o vértice de aceitação, o qual é um problema de alcance. Um ciclo no grafo significa que existe um possível loop infinito na computação. O grafo computacional pode ser de tamanho infinito se não existem restrições de configurações possíveis; na verdade, é fácil ver que existem máquinas de Turing que podem chegar a grandes configurações arbitrariamente. Também é possível ter grafos infinitos: em autômatos finitos, a configuração é composta pela posição da cabeça de leitura e o estado atual, de modo que o grafo de configuração é do tamanho $O(n)$.

Uso da ferramenta

Esta noção é útil, pois reduz os problemas computacionais para problemas de alcance de grafos. Por exemplo, desde que o problema do alcance esteja em NL, podemos representar configurações em espaço logarítmico no tamanho da entrada, e desde que a configuração da máquina de Turing em NL é de fato do tamanho logarítmico, então o alcance dos grafos esta completa para NL. Na outra direção, o que ajuda a verificar a complexidade do modelo de computação; a decisão do problema para um modelo (determinístico) cuja configuração é do espaço logarítmico de acordo com a entrada está em (L) NL. Este é por exemplo o caso do o autômato finito e do autômato finito com um contador.