A theory for Log-Space and NLIN versus co-NLIN

DOI10.2178/JSL/1067620174MaRDI QIDQ4650271zbMATH OpenOpenAlexFDO

Authors Chris Pollett

Publication date 9 February 2005

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

Full work available at URL https://projecteuclid.org/euclid.jsl/1067620174, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.87.9087

zbMATH Keywords

bounded arithmeticindependence resultsMRDP

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 999649
• Separations of theories in weak bounded arithmetic
• An unexpected separation result in Linearly Bounded Arithmetic
• Bounded arithmetic for NC, ALogTIME, L and NL
• scientific article; zbMATH DE number 8798

Cites work

• scientific article; zbMATH DE number 440487 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 3784875 (Why is no real title available?)
• scientific article; zbMATH DE number 575379 (Why is no real title available?)
• scientific article; zbMATH DE number 806747 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 1420845 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• scientific article; zbMATH DE number 3336816 (Why is no real title available?)
• An arithmetical characterization of NP
• End extensions of models of linearly bounded arithmetic
• Rudimentary Predicates and Relative Computation
• Strengths and Weaknesses of LH Arithmetic
• Time-space tradeoffs for satisfiability

This page was built for publication: A theory for Log-Space and NLIN versus co-NLIN

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