Tópico: P, NP, IP, PSPACE... TÓPICO FINAL PARA LEIGOS.

[Tarcísio]

ALGUÉM, POR FAVOR, EXPLICA ESSE MONTE DE SIGLA DE FORMA CLARA, SIMPLES E DIDÁTICA?

[Guinevere]

P - problemas de decisão que possam ser resolvidos em tempo porporcional a um polinônimo sobre o tamanho da entrada (os dados)
NP - problemas de decisão que se tiverem solução a solução possa ser verificada em tempo porporcional a um polinônimo sobre o tamanho da entrada
PSPACE - problemas de decisão que possam ser resolvidos em ESPAÇO (uso de memória) porporcional a um polinônimo sobre o tamanho da entrada

IP - problemas de decisão "resolvíveis" pro um sistema de prova interativo.

[Guinevere]

http://en.wikipedia.org/wiki/IP_(complexity)

http://en.wikipedia.org/wiki/PSPACE

etc

[Tarcísio]

P - problemas de decisão que possam ser resolvidos em tempo proporcional a um polinônimo sobre o tamanho da entrada* (os dados)

NP - problemas de decisão que se tiverem solução a solução possa ser verificada em tempo proporcional a um polinônimo sobre o tamanho da entrada**

PSPACE - problemas de decisão que possam ser resolvidos em ESPAÇO (uso de memória) proporcional a um polinônimo sobre o tamanho da entrada ***

IP - problemas de decisão "resolvíveis" por um sistema de prova interativo****.

*,**,***,**** HEIN?!

[Guinevere]

Um exemplinho da classe P:

Ordenar uma lista de nomes.

Quanto tempo isso leva?

Depende.

Se for uma pessoa fazendo na mão em ordem alfabética leva quanto tempo? Se for um computador? Que computador? Mac? PC? Linux? supercomputador cray? computador de DNA?

A teoria da complexidade se preocupa em medir a dificuldade de um problema sem se importar com os detalhes de quem está resolvendo, se é computador rápido, lento, máquina de calcular ou alguém fazendo no lápis. Ela pergunta "dados n nomes, quanto passos são necessários pra por em ordem?". O quanto cada máquina ou pessoa vai levar pra cada passo é interessante, sim, mas não é isso que a teoria da complexidade pesquisa.

Pra ordenar existem vários métodos. Por exemplo tem um chamado método de ordenação por inserção que toma um número de passos proporcional a n². Isso é um polinômio. Ordenação está em P.

A quantidade de memória usada pode a mesma que serve pra armazar os dados: n. Ordenação está em PSPACE. (n= n¹, né?)

[Guinevere]

PS: o que isso tem a ver com Deus me pergunte no outro tópico)

[Tarcísio]

NP e IP são o quê?

Essa teoria possui fórmulas para cálculos pequenos, sem testar de um-em-um problemas tipo o do Caixeiro Viajante?

[Guinevere]

NP e IP são o quê?

é pra repetir a resposta lá de cima ou colar da dábliopédia?

Essa teoria possui fórmulas para cálculos pequenos, sem testar de um-em-um problemas tipo o do Caixeiro Viajante?

Quê?