Descriptive Complexity of Probabilistic Complexity Classes through Second Order Generalized Quantifiers - Rocha, Thiago Alves; Martins, Ana Teresa (Anais do Encontro de Teoria da Computação (ETC); 2016: Anais do I Encontro de Teoria da Computação, 2016)
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.