Teorema de Savitch

Teorema de Savitch Na teoria da complexidade computacional, Teorema de Savitch, comprovado por Walter Savitch em 1970, dá uma relação entre a complexidade espacial determinística e não determinística. Ele afirma que para qualquer função {barbatana displaystyle Omega (registro(n))} , {estilo de exibição {matemática {NSPACE}}deixei(abandonou(certo)certo)subseteq {matemática {DSPACE}}deixei(abandonou(certo)^{2}certo).} Em outras palavras, se uma máquina de Turing não determinística pode resolver um problema usando {estilo de exibição f(n)} espaço, uma máquina de Turing determinística pode resolver o mesmo problema no quadrado desse limite de espaço.[1] Embora pareça que o não determinismo possa produzir ganhos exponenciais no tempo, este teorema mostra que tem um efeito marcadamente mais limitado sobre os requisitos de espaço.[2] Conteúdo 1 Prova 2 Corolários 3 Veja também 4 Notas 5 Referências 6 Links externos Prova A prova depende de um algoritmo para STCON, o problema de determinar se existe um caminho entre dois vértices em um grafo direcionado, que corre em {estilo de exibição Oleft((log n)^{2}certo)} Espaço para {estilo de exibição m} vértices. A ideia básica do algoritmo é resolver recursivamente um problema um pouco mais geral, testando a existência de um caminho de um vértice s para outro vértice t que usa no máximo k arestas, onde k é um parâmetro que é dado como entrada para o algoritmo recursivo. STCON pode ser resolvido a partir deste problema definindo k para n. Para testar um caminho k-aresta de s para t, pode-se testar se cada vértice u pode ser o ponto médio do caminho s-t, procurando recursivamente por caminhos de metade do comprimento de s para u e u para t. Usando pseudocódigo (na sintaxe do Python) podemos expressar este algoritmo da seguinte forma: def k_edge_path(s, t, k) -> bool: """k inicialmente é igual a n (qual é o número de vértices)""" se k == 0: retorna s == t se k == 1: Retorna (s, t) em arestas para u em vértices: se k_edge_path(s, você, piso(k / 2)) e k_edge_path(você, t, teto(k / 2)): return True return False Esta pesquisa chama a si mesma para uma profundidade de recursão de {estilo de exibição O(log n)} níveis, cada um requer {estilo de exibição O(log n)} bits para armazenar os argumentos da função e variáveis ​​locais nesse nível: k e todos os vértices (s, t, você) exigir {estilo de exibição O(log n)} bits cada. A complexidade total do espaço auxiliar é, portanto, {estilo de exibição Oleft((log n)^{2}certo)} .[Observação 1] Embora descrito acima na forma de um programa em uma linguagem de alto nível, o mesmo algoritmo pode ser implementado com o mesmo espaço assintótico limitado em uma máquina de Turing.

Para ver por que esse algoritmo implica o teorema, considere o seguinte. Para qualquer idioma {estilo de exibição Lin {matemática {NSPACE}}(f(n))} , existe uma máquina de Turing {estilo de exibição M} que decide {estilo de exibição L} no espaço {estilo de exibição f(n)} . Suponha w.l.o.g. o alfabeto é um alfabeto binário {estilo de exibição {0,1}} (a saber. {estilo de exibição Lsubseteq {0,1}^{*}} ). Para qualquer palavra de entrada {estilo de exibição xin {0,1}^{*}} , existe um grafo direcionado {estilo de exibição G_{x}^{M}} cujos vértices são as configurações de {estilo de exibição M} ao executar na entrada {estilo de exibição x} . Pode haver infinitamente muitas dessas configurações; por exemplo. quando {estilo de exibição M} continua escrevendo um símbolo na fita e movendo a cabeça para a direita em um loop, ao infinito. As configurações então crescem arbitrariamente grandes. No entanto, sabemos que no máximo {estilo de exibição esquerdo(certo)} espaço é necessário para decidir se {estilo de exibição xin L} , por isso só nos preocupamos com configurações de tamanho no máximo {estilo de exibição esquerdo(certo)} ; chame qualquer configuração desse tipo admissível. Existem finitamente muitas configurações admissíveis; nomeadamente {estilo de exibição 2 ^{Oleft(f(n)certo)}} . Portanto, o subgrafo induzido {estilo de exibição [G_{x}^{M}]} do {estilo de exibição G_{x}^{M}} contendo (exatamente) as configurações admissíveis tem {estilo de exibição 2 ^{Oleft(f(n)certo)}} vértices. Para cada entrada {estilo de exibição xin {0,1}^{n}} , {estilo de exibição [G_{x}^{M}]} tem um caminho da configuração inicial para uma configuração de aceitação se e somente se {estilo de exibição xin L} . Assim, ao decidir a conectividade em {estilo de exibição [G_{x}^{M}]} , podemos decidir a adesão de {estilo de exibição x} dentro {estilo de exibição L} . Pelo algoritmo acima, isso pode ser feito deterministicamente no espaço {estilo de exibição Oleft(deixei(registro 2^{Oleft(f(n)certo)}certo)^{2}certo)=Esquerda(abandonou(certo)^{2}certo)} ; por isso {estilo de exibição L} é em {estilo de exibição {matemática {DSPACE}}deixei(abandonou(certo)^{2}certo)} .

Como isso vale para todos {barbatana displaystyle Omega (log n)} e tudo {estilo de exibição Lin {matemática {NSPACE}}deixei(abandonou(certo)certo)} , obtemos o enunciado do teorema: Para todas as funções {barbatana displaystyle Omega (log n)} , {estilo de exibição {matemática {NSPACE}}deixei(abandonou(certo)certo)subseteq {matemática {DSPACE}}deixei(abandonou(certo)^{2}certo)} . ^ Observe que pode haver até {estilo de exibição n^{2}} arestas no gráfico de entrada, cada aresta consumindo {estilo de exibição 2log n} espaço, daí o total (ou seja, não apenas auxiliar) complexidade do espaço é {estilo de exibição O(n^{2}log n)} (e este limite é apertado). No entanto, arestas podem ser representadas implicitamente, através da máquina de Turing não determinística sob inspeção. Corolários Alguns corolários importantes do teorema incluem: PSPACE = NPSPACE Isso decorre diretamente do fato de que o quadrado de uma função polinomial ainda é uma função polinomial. Acredita-se que não exista uma relação semelhante entre as classes de complexidade de tempo polinomial, P e NP, embora esta ainda seja uma questão em aberto. NL ⊆ L2 STCON é NL-completo, e assim todas as linguagens em NL também estão na classe de complexidade {estilo de exibição {matemática {cor {Azul}eu}}^{2}={matemática {DSPACE}}deixei(deixei(log nright)^{2}certo)} . See also Exponential time hypothesis Immerman–Szelepcsényi theorem Notes ^ Arora & Barak (2009) p.86 ^ Arora & Barak (2009) p.92 Referências Arora, Sanjeev; Barak, Boaz (2009), Complexidade computacional. Uma abordagem moderna, Cambridge University Press, ISBN 978-0-521-42426-4, Zbl 1193.68112 Papadimitriou, Christos (1993), "Seção 7.3: O Método de Acessibilidade", Complexidade computacional (1st ed.), Addison Wesley, pp. 149-150, ISBN 0-201-53082-1 Savitch, Walter J. (1970), "Relações entre complexidades de fita não determinísticas e determinísticas", Revista de Ciências da Computação e Sistemas, 4 (2): 177-192, doi:10.1016/S0022-0000(70)80006-X, HDL:10338.dmlcz/120475 Sipser, Michael (1997), "Seção 8.1: Teorema de Savitch", Introdução à Teoria da Computação, Publicação PWS, pp. 279-281, ISBN 0-534-94728-X Links externos Lance Fortnow, Fundamentos da Complexidade, Lição 18: Teorema de Savitch. Acessado 09/09/09. Richard J. Lipton, Teorema de Savitch. Dá um relato histórico sobre como a prova foi descoberta. Categorias: Teoria da complexidade estruturalTeoremas na teoria da complexidade computacional