Teoria da complexidade estrutural

Representação pictórica da hierarquia tempo polinomial. As setas indicam a inclusão.

Em Complexidade computacional da ciência da computação, a teoria da complexidade estrutural ou simplesmente complexidade estrutural é o estudo de classes de complexidade, ao invés da complexidade computacional de problemas individuais e algoritmos. Ela envolve a investigação tanto das estruturas internas de várias classes de complexidade quanto das relações entre as diferentes classes de complexidade.

História

A teoria que vem surgindo como resultado de tentativas (não bem sucedidas) de resolver a primeira e ainda a mais importante questão deste tipo, o problema P = NP. A maior parte da pesquisa é feita baseando-se no pressuposto de P não ser igual ao NP e em uma conjectura mais abrangente de que a hierarquia de classes de complexidade de tempo polinomial é infinita.

Importantes resultados

O teorema da compressão

Ver artigo principal: en:Compression theorem

O teorema de compressão é um importante teorema sobre a complexidade das funções computáveis.

O teorema afirma que não existe nenhumaclasse de complexidade maior que todas, com limite computável, que contém todas as funções computáveis.

Teoremas de hierarquia de espaço

Ver artigo principal: Teorema de hierarquia de espaço

Os teoremas de hierarquia espaço são resultados de separação que mostram que tanto as máquinas determinísticas e não determinísticas podem resolver mais problemas em (assintoticamente) mais espaço, sujeito a determinadas condições. Por exemplo, uma máquina de Turing determinística pode resolver mais problemas de decisão no espaço n log n do que no espaço n. Os teoremas análogos um pouco mais fracos para tempo são os teoremas de hierarquia de tempo.

Teoremas de hierarquia de tempo

Ver artigo principal: Teorema de hierarquia de tempo

Os teoremas de hierarquia de tempo são enunciados importantes sobre computação delimitada no tempo em máquinas de Turing. Informalmente, estes teoremas dizem que, dado mais tempo, mais problemas uma máquina de Turing pode resolver. Por exemplo, existem os problemas que podem ser resolvidos com o tempo n², mas não em tempo n.

Teorema de Valiant–Vazirani 

Ver artigo principal: en:Valiant–Vazirani theorem

O teorema de Valiant-Vazirani é um teorema em teoria da complexidade computacional. Foi provado por Leslie Valiant e Vijay Vazirani em seu artigo intitulado NP is as easy as detecting unique solutions publicado em 1986. O teorema indica que, se existe um algoritmo de tempo polinomial para SAT-Não-Ambígua, então, NP = RP. A prova é baseada no lema do isolamento de Mulmuley-Vazirani, que foi posteriormente usado para uma série de aplicações importantes em ciência da computação teórica.

Teorema de Sipser–Lautemann

Ver artigo principal: en:Sipser-Lautemann theorem

O teorema de Sipser-Lautemann ou teorema de Sipser-Gács-Lautemann afirma que a classe de tempo BPP (tempo polinomial probabilístico com erro delimitado), está contida na hierarquia de tempo polinomial, e mais especificamente Σ₂ ∩ Π₂.

Teorema de Savitch

Ver artigo principal: Teorema de Savitch

Teorema de Savitch, provado por Walter Savitch em 1970, dá uma relação entre a complexidade de espaço determinístico e não-determinístico. Ele afirma que para qualquer função $f\in \Omega (\log(n))$,

${\text{NSPACE}}\left(f\left(n\right)\right)\subseteq {\text{DSPACE}}\left(\left(f\left(n\right)\right)^{2}\right).$

Teorema de Toda

Ver artigo principal: en:Toda's theorem

Teorema de Toda é um resultado que foi provado por Seinosuke Toda em seu artigo "PP is as Hard as the Polynomial-Time Hierarchy" (1991) e recebeu o Prêmio Gödel em 1998. O teorema afirma que toda a hierarquia polinomial PH está contida em P^PP; isto implica um enunciado intimamente relacionado, de que PH está contida em P^#P.

Teorema de Immerman–Szelepcsényi

Ver artigo principal: Teorema de Immerman–Szelepcsényi

O teorema de Immerman-Szelepcsenyi foi provado de forma independente por Neil Immerman e Róbert Szelepcsenyi em 1987, pelo qual dividiram o Prêmio Gödel em 1995. Na sua forma geral o teorema afirma que NSPACE(s(n)) = co-NSPACE(s(n)) para toda função s(n) ≥ log n. O resultado é equivalentemente enunciado como NL = co-NL; embora este seja o caso especial quando s(n) = log n, implica o teorema geral por um argumento de preenchimento padrão. O resultado solucionou o segundo problema LBA.

Temas de investigação

As principais linhas de pesquisa nesta área incluem:

• estudo das implicações decorrentes de vários problemas não resolvidos sobre classes de complexidade
• estudo de vários tipos de reduções de restrição de recursos e as linguagens completas correspondentes
• estudo das conseqüências de diversas restrições e os mecanismos de armazenamento e acesso a dados