Qual é a teoria da complexidade computacional?

A teoria da complexidade computacional é uma área de matemática e ciência da computação preocupada 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 recursos de um problema. Alguns problemas podem não ser viáveis ​​nos sistemas de computador existentes devido às suas demandas de recursos. Os pesquisadores classificam problemas por dificuldade e podem dividir os cálculos em problemas polinomiais (P) versus não terminísticos (NP).

Resolver um cálculo 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 do computador 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 solvabilidade de um problema não é necessariamente determinada por sua complexidade, mas noAlgoritmos usados ​​para resolvê -lo.

Na teoria da complexidade computacional, um problema de P é aquele que pode ser resolvido no tempo polinomial com um algoritmo direto. Ainda pode exigir recursos substanciais, mas é solucionável e verificado por computador. Tais problemas podem ser pensados ​​tão rapidamente solucionáveis, desde que um computador tenha os recursos disponíveis para lidar com os cálculos necessários.

Os problemas

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 solucionável dessa maneira, mas exigirá substancialmente mais recursos. Tais problemas podem ser mais fáceis para os operadores humanos capazes de pensar lógico avançado, porque o ponto de inflexão geralmente é de lógica e não dificuldade de computação. O vendedor ambulante profissionalBlem, no qual o objetivo é encontrar a rota mais eficiente entre várias cidades ao longo de uma rota, é um exemplo clássico de um problema de NP na teoria da complexidade computacional.

A classificação de problemas de P versus NP através da teoria da complexidade computacional pode ser uma tarefa complexa, e os problemas podem mudar para frente e para trás pela divisão. Um pequeno conjunto de problemas computacionais não se encaixa perfeitamente em nenhuma das categorias e às vezes é classificada como nenhum para refletir isso. Pode ser possível desenvolver um algoritmo para resolver um problema de NP e, em alguns casos, pode se aplicar a outros problemas que têm 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 ciência da computação que contribui para o desenvolvimento de sistemas avançados de computador de alta potência.