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

DOI10.2178/jsl/1067620174zbMath1059.03067OpenAlexW2805223051MaRDI QIDQ4650271

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

zbMATH Keywords

bounded arithmeticindependence resultsMRDP

Mathematics Subject Classification ID

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

Cites Work

• An arithmetical characterization of NP
• End extensions of models of linearly bounded arithmetic
• Time-space tradeoffs for satisfiability
• Rudimentary Predicates and Relative Computation
• Strengths and Weaknesses of LH Arithmetic
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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