A nonasymptotic lower time bound for a strictly bounded second-order arithmetic

DOI10.1016/J.APAL.2005.12.009zbMATH Open1094.03027OpenAlexW1975429378MaRDI QIDQ2498915

Anatoly Petrivich Beltiukov

Publication date: 16 August 2006

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.apal.2005.12.009

zbMATH Keywords

lower boundsweak arithmeticscomplexity theoryrandom access machine

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Second- and higher-order arithmetic and fragments (03F35) Turing machines and related notions (03D10)

Cites Work

• On the computational power of pushdown automata

Related Items (1)

Improved witnessing and local improvement principles for second-order bounded arithmetic

This page was built for publication: A nonasymptotic lower time bound for a strictly bounded second-order arithmetic

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