Teoria da Complexidade Computacional
A teoria da complexidade computacional classifica problemas pela quantidade de tempo, memória e outros recursos que qualquer algoritmo necessita para resolvê-los, traçando linhas nítidas entre o que é eficientemente solucionável e o que parece ser intratável.
Definition
A teoria da complexidade computacional estuda a dificuldade intrínseca de problemas computacionais, medida pelos recursos, principalmente tempo de execução e memória, necessários para resolvê-los em um modelo como a máquina de Turing, e agrupa os problemas em classes de complexidade de acordo.
Scope
Esta área abrange classes de complexidade de tempo e espaço, como P, NP, PSPACE e a hierarquia polinomial, a teoria da NP-completude e reduções em tempo polinomial, a questão central P versus NP, e modelos com recursos limitados incorporando aleatoriedade, interação e provas, juntamente com os resultados de hierarquia e dificuldade que relacionam essas classes.
Sub-topics
Core questions
- Quanto tempo e memória a resolução de um dado problema inerentemente exige?
- Quais problemas podem ser resolvidos eficientemente e quais parecem resistir a todos os algoritmos eficientes?
- Como os problemas são mostrados como sendo tão difíceis quanto os membros mais difíceis de uma classe de complexidade?
- A aleatoriedade, interação ou não determinismo adicionam poder computacional real?
Key theories
- Teoremas de hierarquia de tempo e espaço
- Dado estritamente mais tempo ou espaço, as máquinas podem resolver estritamente mais problemas, provando que as classes de complexidade formam hierarquias genuínas e que alguns problemas são inerentemente mais difíceis do que outros.
- NP-completude
- O teorema de Cook-Levin identifica problemas em NP aos quais todos os outros problemas NP se reduzem, de modo que um único algoritmo eficiente para qualquer um deles resolveria eficientemente todos eles.
- Modelos com recursos limitados
- Adicionar aleatoriedade, interação ou alternância define classes como BPP, IP e a hierarquia polinomial, cujas relações aprimoram a compreensão do que recursos extras podem e não podem proporcionar.
Clinical relevance
A teoria da complexidade orienta a prática ao certificar quais problemas admitem algoritmos eficientes e quais são NP-difíceis e, portanto, melhor abordados com heurísticas ou aproximação; a suposta dificuldade de certos problemas também sustenta a criptografia moderna, cuja segurança se baseia em tarefas consideradas computacionalmente inviáveis.
History
Hartmanis e Stearns fundaram o campo em 1965, definindo classes de complexidade e provando teoremas de hierarquia. Cook e Levin introduziram a NP-completude por volta de 1971, Karp mostrou muitos problemas naturais completos em 1972, e as décadas seguintes adicionaram modelos de prova randomizados, interativos e probabilisticamente verificáveis.
Key figures
- Stephen Cook
- Richard Karp
- Leonid Levin
- Juris Hartmanis
Related topics
Seminal works
- cook1971
- hartmanisStearns1965
- aroraBarak2009
Frequently asked questions
- Qual a diferença entre computabilidade e complexidade?
- A computabilidade questiona se um problema pode ser resolvido por qualquer algoritmo, ignorando o custo. A complexidade assume que o problema é solucionável e pergunta quão cara essa solução deve ser em tempo e memória, traçando distinções mais finas entre os problemas que são solucionáveis em princípio.
- Por que a NP-completude é importante na prática?
- Quando um problema é demonstrado como NP-completo, ele está ligado a milhares de outros para os quais nenhum algoritmo eficiente é conhecido, apesar de décadas de esforço. Isso sinaliza que a busca por um algoritmo exato rápido é provavelmente inútil e que a aproximação, heurísticas ou métodos para casos especiais são o caminho realista.