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

DOI10.2178/JSL/1067620174zbMATH Open1059.03067OpenAlexW2805223051MaRDI QIDQ4650271FDOQ4650271

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

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

zbMATH Keywords

bounded arithmeticindependence resultsMRDP

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Time-space tradeoffs for satisfiability
• An arithmetical characterization of NP
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Rudimentary Predicates and Relative Computation
• End extensions of models of linearly bounded arithmetic
• Strengths and Weaknesses of LH Arithmetic

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)