The logics for the complexity classes with limited non-determinism

This paper presents the logics with second-order quantifiers that range over relations of polylogarithmic size (log-quantifiers). The logic SOᵖˡᵒᵍ - FO is constituted of the formulas that extend first-order formulas by log-quantifier prefixes. We show that SOᵖˡᵒᵍ - FO collapses to its binary fragment where log-quantifiers range only over unary and binary relations. We further investigate the 0-1 law for SOᵖˡᵒᵍ-FO, demonstrating that it fails in general, yet holds for its monadic existential fragment over the vocabulary that contains only unary relation symbols. Finally, we study the logical characterizations for complexity classes with limited non-determinism. On ordered structures, we show that if a logic L captures a complexity class C, then the logic ^log ᵏ₁- L captures the complexity class GC(log ᵏ⁺¹(n), C), where L ∈ , TC, IFP\. Consequently, ₁ᵖˡᵒᵍ- IFP captures β P on ordered structures.