Conceitos Fundamentais de Teoria da Computação
História da Computação
A História da Computação para uma Máquina de Turing (MT) sobre uma entrada é, simplesmente, a sequência de configurações pelas quais a máquina passa à medida que processa a entrada. É um registro completo da computação dessa máquina.
Autômato Linearmente Limitado (ALL)
É um tipo restrito de MT no qual a cabeça de leitura-escrita não tem permissão para mover-se para fora da parte da fita contendo a entrada. Se a máquina tentar mover sua cabeça para além de qualquer uma das extremidades da entrada, a cabeça permanecerá onde está, da mesma maneira que a cabeça não se moveria para além da extremidade esquerda da fita de uma MT.
Decidibilidade e Computabilidade
- Decidibilidade: É o problema de determinar se uma MT aceita uma determinada entrada (com parada garantida).
- Computabilidade: É a capacidade ou não de determinar um procedimento para solucionar um problema.
Tratabilidade
É todo problema que é decidido por uma MT em tempo polinomial em relação ao tamanho da entrada. Um problema torna-se intratável quando leva um tempo excessivo ou infinito para aceitar ou não uma entrada.
Classes de Complexidade
- P: Reconhecido pelas MT polinomialmente limitadas; cobre a classe das Linguagens Regulares e Livres de Contexto.
- Co-P: Classe de problemas que são o complemento dos problemas de P. A classe Co-P possui a mesma complexidade de P.
- NP: MT Não Determinística (MTND) polinomialmente limitada que possui certificado. Cobre a classe das Linguagens Sensíveis ao Contexto.
- Co-NP: Classe de problemas que contêm os complementos dos problemas NP.
NP-Completo
Uma linguagem B é definida como NP-Completo se:
- B está em NP.
- Toda linguagem A em NP é redutível em tempo polinomial a B.
- Pertencem a NP as linguagens que possuem certificado.
- Somente a classe de complexidade NP possui certificado.
- O termo certificado refere-se a provas verificáveis em tempo polinomial com relação ao tamanho da entrada.
NP-Hard
Mais difícil que NP-Completo, pois não é possível provar o passo 1 da NP-Completude, tornando-os intratáveis. Ou seja, não possuem certificados verificáveis em tempo polinomial com relação ao tamanho da entrada.