Descriptive Complexity of Probabilistic Complexity Classes through Second Order Generalized Quantifiers

  • Thiago Alves Rocha IFCE / UFC
  • Ana Teresa Martins UFC

Resumo


Complexidade Descritiva lida com a relação entre definibilidade lógica e complexidade computational em estruturas finitas. Como exemplo no caso de classes de complexidade probabilísticas, temos que BPP é equivalente à classe de problemas definíveis por uma versão randômica da lógica de ponto-fixo infracionário com contagem BPIFP(C). Neste artigo, nós mostramos que podemos definir lógicas com quantificadores generalizados de segunda ordem equivalentes à classes de complexidade probabilísticas. Estes quantificadores são usados para simular o comportamento de máquinas de Turing probabilísticas.


 

Referências

Andersson, A. (2002). On Second-order Generalized Quantifiers and Finite Structures. Ann. Pure Appl. Logic, 115(1-3):1–32.

Arora, S. and Barak, B. (2009). Computational Complexity: A Modern Approach. Cambridge University Press, New York, NY, USA, 1st edition.

Eickmeyer, K. (2011). Randomness in Complexity Theory and Logics. PhD thesis, Humboldt University of Berlin. http://d-nb.info/1015169163.

Gr¨adel, E., Kolaitis, P. G., Libkin, L., Marx, M., Spencer, J., Vardi, M. Y., Venema, Y., and Weinstein, S. (2005). Finite Model Theory and Its Applications (Texts in Theoretical Computer Science. An EATCS Series). Springer-Verlag New York, Inc., Secaucus, NJ, USA.
Publicado
04/07/2016
ROCHA, Thiago Alves; MARTINS, Ana Teresa. Descriptive Complexity of Probabilistic Complexity Classes through Second Order Generalized Quantifiers. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 1. , 2016, Porto Alegre. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2016 . p. 788-791. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2016.9766.