Antes de mais, peço desculpas antecipadamente por qualquer estupidez. Eu não sou de modo algum um especialista em teoria da complexidade (longe disso! Eu sou um estudante de graduação da minha primeira aula em teoria da complexidade) Aqui está minha pergunta. Agora, o Teorema de Savitch afirma que Agora estou curioso para saber se esse limite inferior foi apertado, isto é, algo como não é possível. NSPACE ( f ( n ) ) ⊆ DSPACE ( ( f ( n ) ) 1.9 )
Parece que deve haver um argumento combinatório direto a ser feito aqui - cada nó no gráfico de configuração de uma máquina de Turing Deterministic possui apenas uma borda de saída, enquanto cada nó no gráfico de configuração de uma máquina de Turing não determinística pode ter mais de uma borda de saída. O que o algoritmo de Savitch está fazendo é converter gráficos de configuração com qualquer número de aresta de saída em gráficos de configuração com arestas de saída.
Como o gráfico de configuração define uma TM exclusiva (não tenho certeza disso), o tamanho combinatório da última é quase certamente maior que a anterior. Essa "diferença" é talvez um fator de , talvez menos - eu não sei. Obviamente, existem muitos pequenos problemas técnicos a serem resolvidos, como como você precisa garantir que não haja loops e assim por diante, mas minha pergunta é se essa é uma maneira razoável de começar a provar algo assim.