y= 2xVS.y= 3x

DOI10.2307/2275554zbMath0882.03032OpenAlexW1970589320MaRDI QIDQ4358061

Alexei P. Stolboushkin, Damian Niwinski

Publication date: 28 September 1997

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275554

zbMATH Keywords

circuit complexitysize of a finite model

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13)

Cites Work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Weak Second‐Order Arithmetic and Finite Automata
• Parity, circuits, and the polynomial-time hierarchy
• A logic for constant-depth circuits
• Languages that Capture Complexity Classes