Conceitos Fundamentais de Complexidade Computacional

Definições Básicas

• Comp: Todo problema computável por uma MT. Não há garantia sobre decidibilidade ou complexidade de tempo.
• Dec: Problemas decidíveis por uma MT, independentemente da complexidade de tempo.
• Tratável: Problema decidível por uma MT em tempo polinomial em relação à entrada.
• Tratabilidade Teórica: Envolve problemas tratáveis tanto por MTD quanto por MTND.
• Tratabilidade Prática: Envolve apenas problemas tratáveis por uma MTD.

Uma MTND é uma extensão de uma MTD, e sua simulação possui complexidade O(2^n). Portanto, problemas tratáveis por MTND existem apenas do ponto de vista teórico.

Hierarquia de Complexidade

2. log n, √n, n/2, n, n log n, n² log n, n³, 2ⁿ, n!

3. O(n) + O(n²/3) + O(n) = O(n²)

4. V, F, V, F, V, V, F, F, V, F

Classes de Complexidade

• Classe P: Problemas decidíveis em tempo polinomial por uma MTD.
• Classe co-P: Complemento dos problemas de P. Possui a mesma complexidade de tempo de P.
• Classe NP: Problemas decidíveis em tempo polinomial por uma MTND.
• Classe NP-Completo: Problemas "mais difíceis" em NP. Se um problema em NP pode ser reduzido polinomialmente a um problema NP-Completo, ele também é NP-Completo.
• Classe co-NP: Complemento dos problemas NP.
• Exp: Problemas decidíveis em tempo exponencial por uma MTND.
• NP-Hard: Problemas pelo menos tão difíceis quanto os mais difíceis em NP.

Relações entre Classes

• a) P = co-P: O complemento de um problema P possui a mesma complexidade de tempo que P.
• b) P ⊆ NP: A classe P está contida em NP. P é um caso particular de NP sem não determinismo.
• c) NP ≠ co-NP: Implica que o complemento de NP não é necessariamente decidível na mesma complexidade de tempo de NP.

Exemplo de Verificação (SAT)

a. Seja M uma MTD, L={w | M aceita w sse <w,c>}, sendo w o conjunto de cláusulas e c um certificado válido contendo os valores verdade de cada variável lógica.

w, c ∈ Σ={(,), ,, 0, 1, V, ^, ¬, V, F}*

Codifique cada variável lógica em binário. Em w, coloque cada cláusula com suas variáveis codificadas; em c, armazene o certificado com cada variável seguida de seu valor verdade.

b. Funcionamento da MT:

• Fita 1: Armazena a entrada w.
• Fita 2: Armazena o certificado c.
• Fita 3: Armazena as cláusulas com variáveis substituídas pelos valores verdade.

Para cada cláusula, substitua as variáveis pelos valores da Fita 2 na Fita 3. Se o símbolo ¬ preceder uma variável, inverta seu valor. Se, após a varredura, alguma cláusula resultar em F, rejeite; caso contrário, aceite.

Exemplo: W=(1 V ¬10 V 11) ^ (10 V ¬11 V 100) / C= 1V, 10F, 11F, 100V