Teoria da Complexidade

Uma classe de complexidade agrupa problemas de decisão pelo recurso que basta para resolvê-los. Aqui o recurso é tempo: algoritmo determinístico em nᵏ, ou verificador polinomial equivalente a uma máquina de Turing não determinística.

O mapa P ⊆ NP, os algoritmos em nᵏ, o certificado e as reduções ≤ₚ deste tópico partem dessa classificação.

As páginas se agrupam em quatro blocos. O primeiro monta o mapa das quatro classes e marca quais inclusões valem, inclusive a recusa de NP ⊆ NP-difícil.

O segundo decide se um procedimento determinístico cabe em nᵏ no comprimento da entrada: Euclides, busca em largura, Dijkstra.

O terceiro define NP pelas duas escritas equivalentes — ramificação não determinística e verificador com certificado — e coloca um problema na classe conferindo o testemunho.

O quarto prova completeza: L está em NP e SAT ≤ₚ L, via Cook–Levin e Karp.

Classes P, NP, NP-completo e NP-difícil lê CAM ∈ P no mapa. Algoritmos de Tempo Polinomial prova CAM ∈ P pela busca em largura em |V|+|E|.

Tempo determinístico nᵏ está em Algoritmos de Tempo Polinomial. Máquina não determinística, ou o par verificador + certificado de tamanho polinomial, está em Algoritmos de Tempo Polinomial Não Determinístico.

Definir NP e conferir soma de subconjuntos está em Algoritmos de Tempo Polinomial Não Determinístico. Colocar TSP e clique nas versões de decisão, pelo certificado, sem redefinir NP-completo, está em Problemas NP Adicionais.

L ∈ NP e SAT ≤ₚ L, Cook–Levin e 3-SAT ≤ₚ CLIQUE estão em Problemas NP-Completos. Só o certificado de ciclo hamiltoniano de custo ≤ k ou de clique de tamanho ≥ k, sem a redução, está em Problemas NP Adicionais.