O que é a teoria da complexidade computacional?
A teoria da complexidade computacional é uma área da matemática e da ciência da computação que se preocupa com os recursos necessários para resolver problemas em um sistema de computador. Várias técnicas estão disponíveis para determinar os requisitos de recurso de um problema. Alguns problemas podem não ser viáveis em sistemas de computadores existentes por causa de suas demandas de recursos. Os pesquisadores classificam os problemas por dificuldade e podem dividir os cálculos em problemas polinomiais (P) versus polinomiais não-términos (NP).
A resolução de uma computação requer recursos como tempo, espaço de armazenamento e hardware. Um sistema de computador pode ter limitações que tornam um problema funcionalmente impossível de resolver porque não possui os recursos disponíveis. À medida que a tecnologia de computadores melhora, um problema anteriormente insolúvel pode se tornar solucionável com a ajuda de novas tecnologias e pesquisas no campo da teoria da complexidade computacional. A resolubilidade de um problema não é necessariamente determinada por sua complexidade, mas pelos algoritmos usados para resolvê-lo.
Na teoria da complexidade computacional, um problema P é aquele que pode ser resolvido em tempo polinomial com um algoritmo direto. Pode ainda exigir recursos substanciais, mas é solucionável e verificável por computador. Tais problemas podem ser considerados tão rapidamente solucionáveis, desde que um computador tenha os recursos disponíveis para lidar com os cálculos necessários.
Os problemas de NP são mais complexos. Não é possível aplicar um único algoritmo e pode ser necessário usar opções mais avançadas, como máquinas de Turing paralelas que podem explorar várias opções. O problema pode ser solucionado dessa maneira, mas exigirá substancialmente mais recursos. Tais problemas podem ser mais fáceis para operadores humanos capazes de raciocínio lógico avançado, porque o ponto de inflexão costuma ser o de lógica e não de pura dificuldade de computação. O problema do vendedor ambulante, em que o objetivo é encontrar a rota mais eficiente entre várias cidades ao longo de uma rota, é um exemplo clássico de um problema de PN na teoria da complexidade computacional.
A classificação dos problemas P versus NP através da teoria da complexidade computacional pode ser uma tarefa complexa, e os problemas podem mudar de um lado para o outro na divisão. Um pequeno conjunto de problemas computacionais não se encaixa perfeitamente em nenhuma das categorias e às vezes é classificado como nenhum para refletir isso. Eventualmente, pode ser possível desenvolver um algoritmo para resolver um problema de NP e, em alguns casos, pode se aplicar a outros problemas que possuem uma estrutura semelhante. Em outros, no entanto, pode ser específico do problema. O processo de explorar esses programas e desenvolver abordagens para resolvê-los é uma área importante da matemática e da ciência da computação que contribui para o desenvolvimento de sistemas de computadores avançados e de alta potência.