BDBComp
Parceria:
SBC
Lógicas Modais e Complexidade Descritiva

Cibele Matos FreireAna Teresa Martins

Na Complexidade Computacional, medimos a eficiência de um algoritmo pelo tempo e espaço dispendido em sua execução, induzindo a definição de classes de problemas. Em 1974, Fagin demonstrou que a classe NP é aquela cujos problemas são descritos pela lógica de segunda-ordem existencial. Este resultado mostrou que a complexidade de um problema pode ser caracterizado por um viés independente da máquina, através da expressividade de uma linguagem capaz de definir uma classe a qual este problema pertence, e lançou a área de Complexidade Descritiva. Estamos aqui interessados no papel dos operadores modais das lógicas K, S4, S5, CTL e CTL* na expressão de problemas de decisão e caracterização de classes de problemas.

http://www.lbd.dcc.ufmg.br/colecoes/enia/2009/048.pdf

Caso o link acima esteja inválido, faça uma busca pelo texto completo na Web: Buscar na Web

Biblioteca Digital Brasileira de Computação - Contato: bdbcomp@lbd.dcc.ufmg.br
     Mantida por:
LBD