What type of study is this?

This is a Quantitative Study study.

September 19, 2025

The logics for the complexity classes with limited non-determinism

Puntos clave

The study reveals that the logic SO^plog-FO collapses to its binary fragment, emphasizing its restrictions.
Evidence suggests the 0-1 law fails for SO^plog-FO but holds for its monadic existential fragment using unary relations.
Analysis of complexity classes shows capturing relationships with logics and their implications for ordered structures.
Results indicate that Σ^log^k_1-IFP captures βP on ordered structures, linking logics to complexity insights.

Resumen

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.

Me gusta

Guardar