Strengths and Weaknesses of LH Arithmetic

DOI10.1002/1521-3870(200202)48:2%3C221::AID-MALQ221%3E3.0.CO;2-VMaRDI QIDQ4531087zbMATH OpenOpenAlexFDO

Authors Chris Pollett, R. Pruim

Publication date 24 July 2002

Full work available at URL https://doi.org/10.1002/1521-3870(200202)48:2%3C221::aid-malq221%3E3.0.co;2-v

zbMATH Keywords

bounded arithmeticfeasible lower boundsindependence

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• The polynomial and linear time hierarchies in V⁰
• The Polynomial and Linear Hierarchies in V0
• scientific article; zbMATH DE number 4059391
• Bounded arithmetic for NC, ALogTIME, L and NL
• Relating the bounded arithmetic and polynomial time hierarchies

Cited in

(2)

• The polynomial and linear time hierarchies in V⁰
• A theory for Log-Space and NLIN versus co-NLIN

This page was built for publication: Strengths and Weaknesses of LH Arithmetic

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