Conceitos Essenciais de Decidibilidade e Complexidade

Capítulo 3: Linguagens e Reconhecimento

• Linguagem Turing-Reconhecível (Recursivamente Enumerável): Aceita por uma Máquina de Turing (MT).
• Linguagem Turing-Decidível (Recursiva): Aceita e rejeita por uma Máquina de Turing (MT).

Capítulo 4: Linguagens Decidíveis

Problemas de Decidibilidade Comuns:

• A_AFD, A_AFN (Aceitação por Autômatos Finitos).
• A_EXP.REG: Se uma expressão regular gera uma dada cadeia.
• V_AFD: Se um Autômato Finito Determinístico (AFD) aceita alguma cadeia (Teste de Vacuidade).
• EQ_AFD: Se a linguagem aceita por um AFD é igual à linguagem aceita por outro AFD.
• A_GLC: Se uma Gramática Livre-do-Contexto (GLC) gera uma cadeia específica.
• V_GLC: Se uma GLC gera alguma cadeia (Teste de Vacuidade).

Propriedades de Fechamento:

• A classe das linguagens regulares é fechada sob as operações de complementação, união e interseção.
• Toda Linguagem Livre-do-Contexto é decidível.

Teoremas Fundamentais:

• Teorema 4.11: "A_MT é indecidível."
• Teorema 4.12: "Uma linguagem é decidível se e somente se ela é Turing-reconhecível e co-Turing-reconhecível."

Capítulo 5: Indecidibilidade e Redução

Reduções Comuns de Indecidibilidade:

*REGULAR_MT: Se uma MT reconhece uma linguagem regular (se existe um AFD equivalente).

Princípios de Redução:

• Teorema da Redução: "Se A ≤_m B e A é 'algo' (e.g., indecidível), então B é 'algo'."
• Teorema: "EQ_MT não é nem Turing-reconhecível nem co-Turing-reconhecível."

Capítulo 7: Complexidade de Tempo (P e NP)

• T. 7.8 (Simulação de Fitas): Seja t(n) uma função, onde t(n) ≥ n. Toda MT Multifita de tempo t(n) tem uma MT de fita única equivalente de tempo O(t²(n)).
• T. 7.11 (Simulação ND para Det.): Seja t(n) uma função, onde t(n) ≥ n. Para toda MT Não Determinística (ND) de fita única de tempo t(n), existe uma MT Determinística (Det.) de fita única de tempo 2^O(t(n)).

Classes de Complexidade:

• D. 7.12: P é a classe de linguagens que são decidíveis em tempo polinomial sobre uma MT Determinística de fita única.
• D. 7.19: NP é a classe das linguagens que têm verificadores de tempo polinomial.
• T. 7.20: Uma linguagem está em NP se e somente se ela é decidida por alguma MT Não Determinística de tempo polinomial.

NP-Completo:

• D. 7.34: Uma linguagem B é NP-Completa se satisfaz duas condições:
  1. B está em NP.
  2. Toda linguagem A em NP é redutível em tempo polinomial a B (A ≤_p B).
• T. 7.35: Se B for NP-Completa e B pertence a P, então P = NP.
• T. 7.36: Se B for NP-Completa e B ≤_p C, e C pertence a NP, então C é NP-Completa.

Capítulo 8: Complexidade de Espaço (PSPACE e NL)

• Teorema de Savitch: Para qualquer função f: N → R, onde f(n) ≥ n, NSPACE(f(n)) ⊆ SPACE(f²(n)).

  Interpretação: Uma MT Determinística utiliza somente o quadrado do espaço da sua MT Não Determinística equivalente.

Classes de Complexidade de Espaço:

• D. 8.6: PSPACE é a classe das linguagens que são decidíveis em espaço polinomial por uma MT Determinística.
• D. 8.8: PSPACE-Completa: Uma linguagem B é PSPACE-Completa se satisfaz duas condições:
  1. B está em PSPACE.
  2. Toda linguagem A em PSPACE é redutível em tempo polinomial a B (A ≤_p B).
• D. 8.22: NL-Completa: Uma linguagem B é NL-Completa se:
  1. B está em NL (Espaço Logarítmico Não Determinístico).
  2. Toda linguagem A em NL é redutível em espaço logarítmico a B.

Propriedades e Resultados Chave:

• PSPACE é fechado sob união, complementação e estrela.
• NL é fechado sob união, interseção e estrela (similar a AFN).
• Se toda linguagem NP-Difícil é também PSPACE-Difícil, então PSPACE = NP.
• A_ALL (Aceitação de todas as cadeias) é PSPACE-Completa.
• A_AFD pertence a L (Espaço Logarítmico Determinístico).
• A_AFN é NL-Completo.
• V_AFD é NL-Completo.
• 2SAT é NL-Completo.