Completo (complexidade)

Na teoria da complexidade computacional, um problema computacional é completo para a classe de complexidade se ele está, tecnicamente falando, entre os "mais difíceis" (e os "mais expressivos") problemas da classe de complexidade.

Mais formalmente, um problema p é chamado de difícil para a classe de complexidade C diante de um tipo dado de redução, se existir tal redução de um problema em C para p. Se o problema é díficil para a classe e ele também é um membro da classe, então ele é completo para esta classe (através deste tipo de redução).

Um problema que é completo para a classe C é chamado de C-completo, e a classe de todos os problemas completos para C é denotado C-completo. A primeira classe completa que foi definida e também a mais conhecida é a classe NP-completo, que contém vários problemas difíceis para resolver na prática. De maneira similar, um problema difícil para a classe C é chamado de C-hard, ex: NP-hard.

Normalmente se assume que a redução em questão não tem uma complexidade computacional mais alta que a própria classe. Portanto pode ser dito que se um problema C-completo tem uma solução "computacional fácil", então todos os problemas "C" também têm uma solução computacional "fácil".

Geralmente, as classes de complexidade que são recursivamente enumeráveis possuem problemas completos, enquanto que as classes que não são recursivamente enumeráveis, não têm até o momento nenhum problema completo conhecido. Por exemplo, as classes NP, co-NP, PLS, PPA todas têm problemas completos, enquanto RP, ZPP, BPP e TFNP não têm nenhum problema completo conhecido (embora algum problema completo pode ser descoberto no futuro).

Existem classes sem problemas completos. Por exemplo, Sipser mostrou que existe uma linguagem M na qual BPP^M (BPP com Máquina oráculo M) sem nenhum problema completo.