21 citations · 116 across the 38 of their papers we have counts for
Showing 2016Show all
2 papers · 1 filter
cs.LO2016★ 12 cited
On Quantified Propositional Logics and the Exponential Time Hierarchy
Miika Hannula, Juha Kontinen, Martin Lück +1
We study quantified propositional logics from the complexity theoretic point of view. First we introduce alternating dependency quantified boolean formulae (ADQBF) which generalize…
cs.CC2016★ 4 cited
Descriptive Complexity of Functions
Arnaud Durand, Anselm Haak, Juha Kontinen +1
We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free fu…