Descriptive Complexity of Probabilistic Complexity Classes through Second Order Generalized Quantifiers

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

DOI: https://doi.org/10.5753/etc.2016.9766

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.