y= 2xVS.y= 3x

DOI10.2307/2275554MaRDI QIDQ4358061zbMATH OpenOpenAlexFDO

Authors Alexei P. Stolboushkin, Damian Niwiński

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

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

Recommendations

• scientific article; zbMATH DE number 3106494
• THE EQUATIONS 3x²−2 = y² AND 8x²−7 = z²
• scientific article; zbMATH DE number 991406
• On the equation \(y^2 = x^3 - pqx\)
• scientific article; zbMATH DE number 3232013
• scientific article; zbMATH DE number 1543098
• What Are x and y?

Cites work

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

Cited in

(1)

• What Are x and y?

This page was built for publication: y= 2xVS.y= 3x

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4358061)