The logics for the complexity classes with limited non-determinism

Abstract This paper presents the logics with second-order quantifiers that range over relations of polylogarithmic size (log-quantifiers). The logic SO^plog - FO is constituted of the formulas that extend first-order formulas by log-quantifier prefixes. We show that SO^plog - 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^plog-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 ^ ^{k}₁- L captures the complexity class GC (^k+1 (n), C), where L \DTC, TC, IFP\. Consequently, ₁^plog- IFP captures P on ordered structures.