Lógicas Modais e Complexidade Descritiva - Freire, Cibele Matos; Martins, Ana Teresa (Anais do Encontro Nacional de Inteligência Artificial e Computacional (ENIAC); 2009: Anais do VII Encontro Nacional de Inteligência Artificial, 2009)
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.