Resumos LEIC-A
IST LEIC-AGitHub
Edit page

Complexidade Computacional

A computação é uma tarefa que consome recursos. Os recursos que mais usualmente são considerados são o tempo (a duração da computação) e o espaço (uma medida da informação que é armazenada/consumida durante a computação), mas também é possível considerar outras quantidades, como a energia (necessária para executar a computação).
A complexidade computacional consiste no estudo dos recursos necessários para resolver um problema.

Podemos calcular a eficiência de uma máquina de Turing (que seja um classificador) relativamente ao tempo e ao espaço de forma relativamente simples, se tomarmos o número de passos de cada computação como uma medida do tempo, e o número de células de memória lidas/escritas ao longo de cada computação como uma medida de espaço.

Definição

Para uma máquina classificadora MM definimos as funções time⁡M,space⁡M:N→N\op{time}_M, \op{space}_M : \mathbb{N} \to \mathbb{N} da seguinte forma:

  • time⁡M(n)\op{time}_M(n) é o comprimento máximo - ou seja, o número de passos máximo - de uma computaçao de MM sobre um input ω\omega com ∣ω∣≤n|\omega| \leq n;
  • space⁡M(n)\op{space}_M(n) é o número máximo de células de memória lidas/escritas durante uma computação de MM sobre um input ω\omega com ∣ω∣≤n|\omega| \leq n.

Para cada n∈Nn \in \mathbb{N}, time⁡M(n)\op{time}_M(n) e space⁡M(n)\op{space}_M(n) dão-nos uma avaliação do pior caso, em termos de duração da computação ou da quantidade de memória necessária, respetivamente, para processar inputs de tamanho limitado por nn.
Mais do que a expressão exacta das funções time⁡M\op{time}_M e space⁡M\op{space}_M associadas a um classificadora MM, estamos interessados em avaliar o seu crescimento. Por essa razão é usual usar notação assintótica, nomeadamente a notação OO (como visto em cadeiras anteriores como IAED ou ASA).

Classes de Complexidade

Agrupamos problemas, de acordo com a sua dificuldade relativa, em classes de complexidade.

Definição

Seja f:N→R0+f : \mathbb{N} \to \mathbb{R}_0^+ uma função. Definem-se as seguintes classes de linguagens:

  • TIME(f(n))={L: existe uma maˊquina M que decide L com time⁡M(n)=O(f(n))}\mathbf{TIME}(f(n)) = \{ L : \text{ existe uma máquina } M \text{ que decide } L \text{ com } \\ \op{time}_M(n) = O(f(n)) \};
  • SPACE(f(n))={L: existe uma maˊquina M que decide L com space⁡M(n)=O(f(n))}\mathbf{SPACE}(f(n)) = \{ L : \text{ existe uma máquina } M \text{ que decide } L \text{ com } \\ \op{space}_M(n) = O(f(n)) \};

Em certas áreas de estudo, são consideradas como eficientes as máquinas cujo comportamento é limitado por um polinómio. Por outro lado, o protótipo das máquinas ineficientes é precisamente o crescimento exponencial. Estas considerações levam à definição das seguintes classes de complexidade:

Definição

Definem-se as seguintes classes de linguagens, em relação ao tempo:

  • P=⋃k∈NTIME(nk)\mathbf{P} = \bigcup_{k \in \mathbb{N}} \mathbf{TIME}(n^k);
  • EXPTIME=⋃k∈NTIME(2nk)\mathbf{EXPTIME} = \bigcup_{k \in \mathbb{N}} \mathbf{TIME}(2^{n^k}).

analogamente, para o espaço, definimos

  • PSPACE=⋃k∈NSPACE(nk)\mathbf{PSPACE} = \bigcup_{k \in \mathbb{N}} \mathbf{SPACE}(n^k);
  • EXPSPACE=⋃k∈NSPACE(2nk)\mathbf{EXPSPACE} = \bigcup_{k \in \mathbb{N}} \mathbf{SPACE}(2^{n^k}).

Relação entre função tempo e espaço

Para uma máquina classificadora MM, tem-se que time⁡M\op{time}_M e space⁡M\op{space}_M são funções monótonas e, para qualquer, n∈Nn \in \mathbb{N}:

  1. space⁡M(n)≤time⁡M(n)\op{space}_M(n) \leq \op{time}_M(n)
  2. time⁡M(n)≤2O(space⁡M(n))\op{time}_M(n) \leq 2^{O(\op{space}_M(n))}.
Prova

O facto de as funções time⁡M\op{time}_M e space⁡M\op{space}_M serem monótonas segue da definição.

(1) A primeira propriedade vem apenas do facto de que, para escrever numa célula de memória de memória, é necessário deslocarmo-nos para essa célula. Desta forma, o número de passos de uma computação é pelo menos igual ao número de células escritas.

(2) Considere-se a computação da máquina de Turing MM com alfabeto de trabalho Γ\Gamma e conjunto de estados QQ, sobre um input de comprimento menor ou igual a nn.
Temos que MM é classificadora pelo que a sua computação termina sempre. Verificamos que a computação de MM não pode passar duas vezes pela mesma configuração: se isto acontecesse, a máquina entraria em ciclo infinito uma vez que todas as transições são deterministas. Sendo assim, o tempo que a máquina demora a fazer a sua computação está majorado pelo seu número de configurações.
Seja m=spaceM(n)m = space_M(n). Temos então que o número de configurações é definido por:

  • o conteúdo na fita, que é no máximo ∣Γ∣m|\Gamma|^m;
  • a posição da cabeça de leitura/escrita, que pode estar numa de mm posições;
  • o estado em que a computação se encontra, que é um de ∣Q∣|Q|.

Desta forma, o número de estados é majorado por ∣Γ∣m×∣Q∣×m|\Gamma|^m \times |Q| \times m.
Então:

time⁡M(n)≤∣Γ∣m×∣Q∣×m≤2mlog⁡2(∣Γ∣)⋅2log⁡2(∣Q∣)⋅2m=2m(log⁡2(∣Γ∣)+1)+log⁡2(∣Q∣)=2O(space⁡M(n))\begin{align*} \op{time}_M(n) &\leq |\Gamma|^m \times |Q| \times m \leq 2^{m\log_2(|\Gamma|)} \cdot 2^{\log_2(|Q|)} \cdot 2^m \\ &= 2^{m(\log_2(|\Gamma|) + 1) + \log_2(|Q|)} = 2^{O(\op{space}_M(n))} \end{align*}

Corolário

P⊂PSPACE⊂EXPTIME⊂EXPSPACE\mathbf{P} \subset \mathbf{PSPACE} \subset \mathbf{EXPTIME} \subset \mathbf{EXPSPACE}

Variantes

Movimentos-SS

Proposição

Toda a máquina de Turing MM com transições-SS é equivalente a uma máquina de Turing TT sem transições-SS tal que time⁡T(n)=O(time⁡M(n))\op{time}_T(n) = O(\op{time}_M(n)) e space⁡T(n)=O(space⁡M(n))\op{space}_T(n) = O(\op{space}_M(n))

Prova

Na prova da equivalência, simulamos todos os movimentos-SS com um movimento à direita seguido de um movimento à esquerda. Temos então que cada movimento em MM corresponde no máximo a dois movimentos em TT pelo que

time⁡T(n)≤2time⁡M(n)=O(time⁡M(n))\op{time}_T(n) \leq 2 \op{time}_M(n) = O(\op{time}_M(n)) \\
space⁡T(n)≤space⁡M(n)+1=O(space⁡M(n))\op{space}_T(n) \leq \op{space}_M(n) + 1 = O(\op{space}_M(n))

Bidirecional

Proposição

Toda a máquina bidirecional MM é equivalente a uma máquina unidirecional TT tal que time⁡T(n)=O(n+time⁡M(n)2)\op{time}_T(n) = O(n + \op{time}_M(n)^2) e space⁡T(n)=O(space⁡M(n))\op{space}_T(n) = O(\op{space}_M(n))

Prova

Vamos basear-nos na prova de equivalência apresentada no capítulo de Máquinas de Turing.
A computação de TT começa por balizar o input com os símbolos II e FF, fazendo 2n+32n + 3 passos.
O resto da computação é idêntica a MM, exceto nos casos em que é necessário introduzir espaçamento. Para introduzir espaço à direita precisamos apenas de 3 movimentos, enquanto que à esquerda precisamos de copiar a palavra toda, o que implica O(space⁡M(n))O(\op{space}_M(n)) passos.
No final há que apagar o delimitador FF, o que demora O(space⁡M(n))O(\op{space}_M(n)). Na pior das hipóteses, temos que é preciso abrir espaço à esquerda em cada passo, pelo que:

time⁡T(n)≤(2n+3)+time⁡M(n)⋅O(space⁡M(n))+O(space⁡M(n))≤O(n)+time⁡M(n)⋅O(time⁡M(n))+O(time⁡M(n))=O(n+time⁡M(n)2+time⁡M(n))=O(n+time⁡M(n)2)\begin{align*} \op{time}_T(n) &\leq (2n+3) + \op{time}_M(n) \cdot O(\op{space}_M(n)) + O(\op{space}_M(n)) \\ &\leq O(n) + \op{time}_M(n) \cdot O(\op{time}_M(n)) + O(\op{time}_M(n)) \\ &= O(n + \op{time}_M(n)^2 + \op{time}_M(n)) \\ &= O(n + \op{time}_M(n)^2) \end{align*}

Quando ao espaço, TT usa apenas mais duas células, as que usa para delimitar a palavra. Então:

space⁡T(n)≤2+space⁡M(n)=O(space⁡M(n))\op{space}_T(n) \leq 2 + \op{space}_M(n) = O(\op{space}_M(n))

Multifita

Proposição

Toda a máquina de Turing multifita MM é equivalente a uma máquina com apenas uma fita TT tal que time⁡T(n)=O(n+time⁡M(n)2)\op{time}_T(n) = O(n + \op{time}_M(n)^2) e space⁡T(n)=O(space⁡M(n))\op{space}_T(n) = O(\op{space}_M(n))

Prova

Atente-se na máquina TT construída a partir de MM tal como no capítulo de Máquinas de Turing.
A computação de TT começa por inicializar a fita de memória, balizando o input com os símbolos II e FF, e demarcando o espaço de cada uma das kk fitas da máquina TT, num número de passos da ordem de O(n+k)O(n + k), onde nn é o tamanho do input e kk o número de fitas.
De seguida simula cada uma das transições de MM, percorrendo a fita da esquerda para a direita de forma a ler os símbolos marcados, e depois da direita para a esquerda atualizando as marcações, visitando um número de células da ordem de O(space⁡M(n))O(\op{space}_M(n)). Pode ter de efetuar um máximo de kk espaçamentos, 1 em cada fita, visitando assim um número máximo de células da ordem de k⋅O(space⁡M(n))k \cdot O(\op{space}_M(n)).
Finalmente, após a aceitação por MM, os símbolos marcados são adequadamente substituídos, e o símbolo FF é removido, o que de novo implica que um número de células da ordem de O(space⁡M(n))O(\op{space}_M(n)) seja visitado.
Assim, temos:

time⁡T(n)≤O(n+k)+time⁡M(n)⋅(O(space⁡M(n))+kO(space⁡M(n)))+O(space⁡M(n))≤O(n)+time⁡M(n)⋅O(time⁡M(n))+O(time⁡M(n))=O(n+time⁡M(n)2)\begin{align*} \op{time}_T(n) &\leq O(n+k) + \op{time}_M(n) \cdot \left( O(\op{space}_M(n)) + k O(\op{space}_M(n)) \right) \\ &\quad + O(\op{space}_M(n)) \\ &\leq O(n) + \op{time}_M(n) \cdot O(\op{time}_M(n)) + O(\op{time}_M(n)) \\ &= O(n + \op{time}_M(n)^2) \end{align*}

Quanto ao espaço, a máquina TT usa exatamente k+1k+1 células de memória adicionais, pelo que:

space⁡T(n)=k+1+space⁡M(n)=O(space⁡M(n))\op{space}_T(n) = k+1+\op{space}_M(n) = O(\op{space}_M(n))

Não-Determinismo

No caso das máquinas não-deterministas vai surgir a primeira diferença substancial relativamente à teoria da computabilidade.

Definição

Seja MM uma máquina não-determinista classificadora. Definem-se as funções ntime⁡M,nspace⁡M:N→N\op{ntime}_M, \op{nspace}_M: \mathbb{N} \to \mathbb{N} da seguinte forma:

  • ntime⁡M(n)\op{ntime}_M(n) é o comprimento do maior ramo de computação de MM sobre um input ω\omega com ∣ω∣≤n| \omega | \leq n;
  • nspace⁡M(n)\op{nspace}_M(n) é o número máximo de células de memória lidas/escritas durante algum dos ramos de computação de MM sobre um input ω\omega com ∣ω∣≤n| \omega | \leq n.

Tal como para as máquinas deterministas, definimos as classes de tempo e espaço não-deterministas:

Definição

Seja f:N→R0+f : \mathbb{N} \to \mathbb{R}_0^+ uma função. Definem-se as seguintes classes de linguagens:

  • NTIME(f(n))={L: existe uma maˊquina na˜o-determinista M que decide L com ntime⁡M(n)=O(f(n))}\mathbf{NTIME}(f(n)) = \{ L : \text{ existe uma máquina não-determinista } \\ M \text{ que decide } L \text{ com } \op{ntime}_M(n) = O(f(n)) \};
  • NSPACE(f(n))={L: existe uma maˊquina na˜o-determinista M que decide L com nspace⁡M(n)=O(f(n))}\mathbf{NSPACE}(f(n)) = \{ L : \text{ existe uma máquina não-determinista } \\ M \text{ que decide } L \text{ com } \op{nspace}_M(n) = O(f(n)) \};

Definição

Definem-se as seguintes classes de linguagens, em relação ao tempo:

  • NP=⋃k∈NNTIME(nk)\mathbf{NP} = \bigcup_{k \in \mathbb{N}} \mathbf{NTIME}(n^k);
  • NEXPTIME=⋃k∈NNTIME(2nk)\mathbf{NEXPTIME} = \bigcup_{k \in \mathbb{N}} \mathbf{NTIME}(2^{n^k}).

analogamente, para o espaço, definimos

  • NPSPACE=⋃k∈NNSPACE(nk)\mathbf{NPSPACE} = \bigcup_{k \in \mathbb{N}} \mathbf{NSPACE}(n^k);
  • NEXPSPACE=⋃k∈NNSPACE(2nk)\mathbf{NEXPSPACE} = \bigcup_{k \in \mathbb{N}} \mathbf{NSPACE}(2^{n^k}).

Uma vez que máquinas deterministas são casos particulares de máquinas não-deterministas, temos que:

Proposição

P⊂NPPSPACE⊂NPSPACEEXPTIME⊂NEXPTIMEEXPSPACE⊂NEXPSPACE\begin{matrix} \mathbf{P} \subset \mathbf{NP} & \mathbf{PSPACE} \subset \mathbf{NPSPACE} \\ \mathbf{EXPTIME} \subset \mathbf{NEXPTIME} & \mathbf{EXPSPACE} \subset \mathbf{NEXPSPACE} \end{matrix}

A seguinte proposição também transita para máquinas não deterministas:

Proposição

Para uma máquina não-determinista classificadora MM, tem-se que ntime⁡M\op{ntime}_M e nspace⁡M\op{nspace}_M são funções monótonas e, para qualquer, n∈Nn \in \mathbb{N}:

  1. nspace⁡M(N)≤ntime⁡M(n)\op{nspace}_M(N) \leq \op{ntime}_M(n)
  2. ntime⁡M(n)≤2O(nspace⁡M(n))\op{ntime}_M(n) \leq 2^{O(\op{nspace}_M(n))}.
Prova

Idêntica à para máquinas deterministas, quando considerado um ramo específico da computação não determinista.

e consequentemente

Corolário

NP⊂NPSPACE⊂NEXPTIME⊂NEXPSPACE\mathbf{NP} \subset \mathbf{NPSPACE} \subset \mathbf{NEXPTIME} \subset \mathbf{NEXPSPACE}

Finalmente, é importante estabelecer a relação entre a eficiência de máquinas deterministas com máquinas não-deterministas.

Proposição

Toda a máquina de Turing não-determinista NN é equivalente a uma máquina de Turing determinista TT tal que time⁡T(n)=O(n+ntime⁡N(n))⋅2O(ntime⁡N(n))\op{time}_T(n) = O(n + \op{ntime}_N(n)) \cdot 2^{O(\op{ntime}_N(n))} e space⁡T(n)=O(n+ntime⁡N(n))\op{space}_T(n) = O(n + \op{ntime}_N(n))

Prova

Vamos considerar a máquina TT construída a partir de NN como no capítulo de Máquinas de Turing.
A computação de TT começa por inicializar 3 fitas de memória, a segunda das quais com o comprimento máximo das computações possíveis, que pode ser calculado num número de passos da ordem de O(ntime⁡N(n))O(\op{ntime}_N(n)). De seguida, copia o input da primeira para a terceira fita, balizando-o com os símbolos II e FF, e executando um número de passos da ordem de O(n)O(n). Na terceira fita é então simulado o caminho de computação de NN descrito na fita 2, num número de passos inferior ou igual a ntime⁡N(n)\op{ntime}_N(n), após o que volta a limpar a fita 3, visitando um número de células da ordem de O(space⁡N(n))O(\op{space}_N(n)).
Em caso de aceitação por NN, há ainda que, na terceira fita, remover o símbolo FF e colocar a cabeça de leitura/escrita no início da palavra, visitando um número de células da ordem de O(nspace⁡N(n))O(\op{nspace}_N(n)).
Se bb for o número máximo de escolhas não-deterministas na máquina NN, temos assim:

time⁡T(n)≤O(ntime⁡N(n))+bntime⁡N(n)(O(n)+ntime⁡N(n)+O(nspace⁡N(n)))+O(nspace⁡N(n))≤O(ntime⁡N(n))+bntime⁡N(n)(O(n)+O(ntime⁡N(n)))=O(n+ntime⁡N(n))⋅2O(ntime⁡N(n))\begin{align*} \op{time}_T(n) &\leq O(\op{ntime}_N(n)) + b^{\op{ntime}_N(n)} \left( O(n) + \op{ntime}_N(n) + O(\op{nspace}_N(n)) \right) \\ & \quad + O(\op{nspace}_N(n)) \\ &\leq O(\op{ntime}_N(n)) + b^{\op{ntime}_N(n)} \left( O(n) + O(\op{ntime}_N(n)) \right) \\ &= O(n + \op{ntime}_N(n)) \cdot 2^{O(\op{ntime}_N(n))} \end{align*}

Quanto ao espaço, como vimos na secção de máquinas multifita, temos que o espaço numa máquina multifita tem a mesma complexidade que a máquina de Turing com uma fita correspondente, pelo que:

space⁡T(n)≤O(n)+O(ntime⁡N(n))+O(nspace⁡N(n))≤O(n)+O(ntime⁡N(n))+O(ntime⁡N(n))=O(n+ntime⁡N(n))\begin{align*} \op{space}_T(n) &\leq O(n) + O(\op{ntime}_N(n)) + O(\op{nspace}_N(n)) \\ &\leq O(n) + O(\op{ntime}_N(n)) + O(\op{ntime}_N(n)) \\ &= O(n + \op{ntime}_N(n)) \end{align*}

Note-se que isto implica que a existência de uma máquina não-determinista de tempo polinomial para resolver um problema parece não nos poder garantir mais do que uma máquina determinista de tempo exponencial para resolver o mesmo problema.
O problema P vs NP\mathbf{P} \text{ vs } \mathbf{NP} pode ser compreendido como perguntando se é possível fazer esta simulação de forma mais eficiente (polinomial).

Propriedades de Fecho e Redução Polinomial

Proposição

Seja C\mathcal{C} uma das classes de complexidade P\mathbf{P}, NP\mathbf{NP}, PSPACE\mathbf{PSPACE}, NPSPACE\mathbf{NPSPACE}, EXPTIME\mathbf{EXPTIME}, NEXPTIME\mathbf{NEXPTIME}, EXPSPACE\mathbf{EXPSPACE}, NEXPSPACE\mathbf{NEXPSPACE}, e sejam Σ\Sigma um alfabeto, e L1,L2∈CL_1, L_2 \in \mathcal{C} linguagens sobre Σ\Sigma.
Então:

  • ∅∈C\emptyset \in \mathcal{C}
  • Σ∗∈C\Sigma^* \in \mathcal{C}
  • L1∪L2∈CL_1 \cup L_2 \in \mathcal{C}
  • L1∩L2∈CL_1 \cap L_2 \in \mathcal{C}

Se C≠NP\mathcal{C} \neq \mathbf{NP} e C≠NEXPTIME\mathcal{C} \neq \mathbf{NEXPTIME}, então temos também que:

  • L1∖L2∈CL_1 \setminus L_2 \in \mathcal{C}
Prova

É evidente que ∅\emptyset e Σ∗\Sigma^* podem ser decididas em O(1)O(1), pelo que estão contidas nas classes enumeradas.

Quanto as proposições 3 e 4, usamos as máquinas MM como definidas nas prova que L1∩L2L_1 \cap L_2 e L1∪L2L_1 \cup L_2 são decidíveis, para L1L_1 e L2L_2 decidíveis.
Usamos o caso da disjunção como exemplo, mas a conjunção é análoga. Se M1M_1 é computada em O(f(x))O(f(x)) e M2M_2 é computada em O(g(x))O(g(x)), então a máquina MM que decide L1∪L2L_1 \cup L_2 computa em O(f(x)+g(x))O(f(x) + g(x)), o que é suficiente para provar ambas proposições (não em teste!).

A quinta proposição fica como exercício (agradecem-se contribuições).

Stephen Cook e Leonid Levin mostraram que existem algumas linguagens em NP\mathbf{NP} às quais todas as outras linguagens dessa classe se reduzem. Mais ainda, mostraram que essa redução pode ser feita em tempo polinomial de forma que se se encontrar uma solução eficiente para um desses problemas, também se consegue decidir eficientemente qualquer outro problema de NP\mathbf{NP}. Vamos então começar por definir o que é uma redução polinomial de uma linguagem a outra:

Definição

Dadas linguagens sobre L1L_1 e L2L_2 sobre alfabetos Σ1\Sigma_1 e Σ2\Sigma_2, respetivamente, dizemos que há uma redução polinomial de L1L_1 para L2L_2 ou que L1L_1 reduz polinomialmente a L2L_2, o que denotamos por L1≤PL2L_1 \leq_P L_2 se existe uma função total f:Σ1∗→Σ2∗f : \Sigma_1^* \to \Sigma_2^*, calculada por uma máquina determinista em tempo polinomial tal que, para cada ω∈Σ1∗\omega \in \Sigma_1^*

ω∈L1⇔f(ω)∈L2\omega \in L_1 \Leftrightarrow f(\omega) \in L_2

Obviamente, se L1≤PL2L_1 \leq_P L_2, então L1≤L2L_1 \leq L_2.

Proposição

Sejam L1L_1 e L2L_2 linguagens sobre alfabetos Σ1\Sigma_1 e Σ2\Sigma_2, respetivamente. Seja C\mathcal{C} uma das classes de complexidade P\mathbf{P}, NP\mathbf{NP}, PSPACE\mathbf{PSPACE}, NPSPACE\mathbf{NPSPACE}, EXPTIME\mathbf{EXPTIME}, NEXPTIME\mathbf{NEXPTIME}, EXPSPACE\mathbf{EXPSPACE}, NEXPSPACE\mathbf{NEXPSPACE}. Se L1≤PL2L_1 \leq_P L_2 e L2∈CL_2 \in \mathcal{C}, então L1∈CL_1 \in \mathcal{C}.

Prova

As demonstrações são semelhantes para todas as classes. Ilustra-se a demonstração para a classe NP\mathbf{NP}.
Assuma-se então que L1≤PL2L_1 \leq_P L_2 e L2∈NPL_2 \in \mathbf{NP}. Seja NN uma máquina de Turing não-determinista que decide L2L_2 e k≥1k \geq 1 tal que ntime⁡N(n)=O(nk)\op{ntime}_N(n) = O(n^k). Seja MM uma máquina de Turing que calcula ff e l≥1l \geq 1 tal que time⁡M(n)=O(nl)\op{time}_M(n) = O(n^l).
Consideremos a máquina de Turing TT que ao receber um input ω\omega, calcula f(ω)f(\omega) em MM e usa o resultado dessa computação em NN, retornando no final o mesmo que NN. Ora, TT aceita então uma palavra ω\omega se e só se NN aceitar f(ω)f(\omega). Ora, temos que NN aceita f(ω)f(\omega) se e só se f(ω)∈L2f(\omega) \in L_2. Por definição de redução polinomial, isto acontece se e só se ω∈L1\omega \in L_1. Conclui-se então que TT decide L1L_1 (pois termina sempre, uma vez que tanto NN como MM terminam sempre).
Basta-nos então provar que ntime⁡T(n)∈O(nt)\op{ntime}_T(n) \in O(n^t) para algum x∈Nx \in \mathbb{N}. Ora:

ntime⁡T(n)=time⁡M(n)+ntime⁡N(∣f(x)∣)≤time⁡M(n)+ntime⁡N(space⁡M(x))≤time⁡M(n)+ntime⁡N(∣x∣+time⁡M(∣x∣))≤time⁡M(n)+ntime⁡N(n+time⁡M(n))=O(nl)+O((n+O(nl))k)=O(nlk)\begin{align*} \op{ntime}_T(n) &= \op{time}_M(n) + \op{ntime}_N(|f(x)|) \\ &\leq \op{time}_M(n) + \op{ntime}_N(\op{space}_M(x)) \\ &\leq \op{time}_M(n) + \op{ntime}_N(|x| + \op{time}_M(|x|)) \\ &\leq \op{time}_M(n) + \op{ntime}_N(n + \op{time}_M(n)) \\ &= O(n^l) + O((n + O(n^l))^k) \\ &= O(n^{lk}) \end{align*}

Conclui-se então que L1∈NPL_1 \in \mathbf{NP}.

Teorema de Savitch

Teorema de Savitch

Seja f:N→R+f : \mathbb{N} \to \mathbb{R}^+ tal que f(n)≥nf(n) \geq n. Então

NSPACE(f(n))⊂SPACE(f(n)2)\mathbf{NSPACE}(f(n)) \subset \mathbf{SPACE}(f(n)^2)

Corolário

PSPACE=NPSPACE\mathbf{PSPACE} = \mathbf{NPSPACE} e EXPSPACE=NEXPSPACE\mathbf{EXPSPACE} = \mathbf{NEXPSPACE}

Teoremas de Hierarquia

Definição

Uma função f:N→Nf : \mathbb{N} \to \mathbb{N} diz-se construtível no espaço se log⁡(n)=O(f(n))\log(n) = O(f(n)) e se a função que mapeia palavras 1n1^n para a representação binária de f(n)f(n) é computável em espaço O(f(n))O(f(n)).

Todas as funções mais comuns que são pelo menos O(log⁡(n))O(\log(n)), como, por exemplo, log⁡(n)\log(n), nlog⁡(n)n\log(n), nn, n2n^2 e 2n2^n, são construtíveis no espaço.

Definição

Uma função t:N→Nt : \mathbb{N} \to \mathbb{N} diz-se construtível no tempo se nlog⁡(n)=O(t(n))n\log(n) = O(t(n)) e se a função que mapeia palavras 1n1^n para a representação binária de t(n)t(n) é computável em tempo O(t(n))O(t(n)).

Todas as funções mais comuns que são pelo menos O(nlog⁡(n))O(n\log(n)), como, por exemplo, nlog⁡(n)n\log(n), n2n^2 e 2n2^n, são construtíveis no tempo.

Teorema da Hierarquia no Espaço

Seja f:N→Nf : \mathbb{N} \to \mathbb{N} uma função construtível no espaço. Então existe uma linguagem decidível em espaço O(f(n))O(f(n)) mas não em espaço o(f(n))o(f(n)).

Corolário

Sejam f1,f2:N→Nf_1, f_2 : \mathbb{N} \to \mathbb{N} tais que f2(n)f_2(n) é construtível no espaço e f1(n)=o(f2(n))f_1(n) = o(f_2(n)). Então SPACE(f1(n))⊊SPACE(f2(n))SPACE(f_1(n)) \subsetneq SPACE(f_2(n)).

Teorema da Hierarquia no Tempo

Seja t:N→Nt : \mathbb{N} \to \mathbb{N} uma função construtível no tempo. Então existe uma linguagem decidível em tempo O(t(n))O(t(n)) mas não em tempo o(t(n)log⁡(t(n)))o(t(n)\log(t(n))). Este resultado permite-nos separar classes de complexidade temporais.

Corolário

Sejam t1,t2:N→Nt_1, t_2 : \mathbb{N} \to \mathbb{N} tais que t2(n)t_2(n) é construtível no tempo e t1(n)=o(t2(n)log⁡(t2(n)))t_1(n) = o(\frac{t_2(n)}{\log(t_2(n))}). Então TIME(t1(n))⊊TIME(t2(n))TIME(t_1(n)) \subsetneq TIME(t_2(n)).

Dificuldade e Completude

Seja CC uma classe de complexidade. Uma linguagem AA diz-se:

  • CC-difícil se qualquer que seja L∈CL \in C se tem L≤PAL \leq_P A

  • CC-completa se é CC-difícil e A∈CA \in C