Mostrar código-fonte de Teoria da complexidade estrutural

[[Ficheiro:Polynomial_time_hierarchy.svg|right|thumb|350x350px|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 [[Classe de complexidade|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.<ref name="jha">[[Juris Hartmanis]], "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th International Colloquium on Automata, Languages and Programming,  1988 (ICALP 88), ''Lecture Notes in Computer Science'', vol. 317 (1988), pp. 271-286.</ref>

== 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 versus NP|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 [[Hierarquia polinomial|complexidade de tempo polinomial]] é infinita.<ref name="jha">[[Juris Hartmanis]], "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th International Colloquium on Automata, Languages and Programming,  1988 (ICALP 88), ''Lecture Notes in Computer Science'', vol. 317 (1988), pp. 271-286.</ref>

== Importantes resultados ==

=== O teorema da compressão ===
{{main|[[:en:Compression theorem]]}}
O [[Teorema da compressão|teorema de compressão]] é um importante teorema sobre a complexidade das [[Função computável|funções computáveis]].

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

=== Teoremas de hierarquia de espaço ===
{{main|[[Teorema de hierarquia de espaço]]}}
Os [[Teorema de hierarquia de espaço| 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| máquina de Turing determinística]] pode resolver mais[[Problema de decisão| 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[[Teorema de hierarquia de tempo| teoremas de hierarquia de tempo]].

=== Teoremas de hierarquia de tempo ===
{{main|[[Teorema de hierarquia de tempo]]}}
Os [[Teorema de hierarquia de tempo|teoremas de hierarquia de tempo]] são enunciados importantes sobre computação delimitada no tempo em [[Máquina de Turing|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 ===
{{main|[[:en:Valiant–Vazirani theorem]]}}
O [[teorema de Valiant-Vazirani]] é um teorema em [[Complexidade computacional|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.<ref>{{Citar periódico|titulo = NP is as easy as detecting unique solutions|url = http://linkinghub.elsevier.com/retrieve/pii/0304397586901350|jornal = Theoretical Computer Science|paginas = 85-93|volume = 47|doi = 10.1016/0304-3975(86)90135-0|primeiro = L.G.|ultimo = Valiant|coautores = V.V.}}</ref> O teorema indica que, se existe um [[P (complexidade)|algoritmo de tempo polinomial]] para SAT-Não-Ambígua, então, [[RP (complexidade computacional)|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 ===
{{main|[[: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 polinomial|hierarquia de tempo polinomial]], e mais especificamente Σ<sub>2</sub> ∩ Π<sub>2</sub>.

=== Teorema de Savitch ===
{{main|[[Teorema de Savitch]]}}
[[Teorema de Savitch]], provado por [[Walter Savitch]] em 1970, dá uma relação entre a [[DSPACE|complexidade de espaço]] determinístico e não-determinístico. Ele afirma que para qualquer função <math>f\in\Omega(\log(n))</math>,

:<math>\text{NSPACE}\left(f\left(n\right)\right) \subseteq \text{DSPACE}\left(\left(f\left(n\right)\right)^2\right).</math>

=== Teorema de Toda ===
{{main|[[: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 [[PH (complexidade)|hierarquia polinomial PH]] está contida em P<sup>PP</sup>; isto implica um enunciado intimamente relacionado, de que PH está contida em P<sup>#P</sup>.

=== Teorema de Immerman–Szelepcsényi ===
{{main|[[Teorema de Immerman–Szelepcsényi]]}}
O [[Teorema de Immerman–Szelepcsényi|teorema de Immerman-Szelepcsenyi]] foi provado de forma independente por [[Neil Immerman]] e [[Róbert Szelepcsényi|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&nbsp;''n''. O resultado é equivalentemente enunciado como [[Complexidade NL|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 [[Autômato linearmente limitado|segundo problema LBA]].

== Temas de investigação ==
As principais linhas de pesquisa nesta área incluem:<ref name="jha">[[Juris Hartmanis]], "New Developments in Structural Complexity Theory" (invited lecture), Proc. 15th International Colloquium on Automata, Languages and Programming,  1988 (ICALP 88), ''Lecture Notes in Computer Science'', vol. 317 (1988), pp. 271-286.</ref>
* estudo das implicações decorrentes de vários problemas não resolvidos sobre classes de complexidade
* estudo de vários tipos de [[Redução (complexidade)|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

== Referências ==
{{Reflist}}
[[Categoria:Teoria da complexidade estrutural]]