Relativizing small complexity classes and their theories

DOI10.1007/s00037-015-0113-8zbMath1336.68084arXiv1204.5508OpenAlexW2276406710MaRDI QIDQ260396

F. Blanchet-Sadri, M. Dambrine

Publication date: 21 March 2016

Published in: Computational Complexity, Computer Science Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1204.5508

zbMATH Keywords

proof complexitycomplexity classeslogical theoriesrelativized classes

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Descriptive complexity and finite models (68Q19)

Related Items (4)

Towards Computational Complexity Theory on Advanced Function Spaces in Analysis ⋮ Induction rules in bounded arithmetic ⋮ The complexity of the comparator circuit value problem ⋮ Relativizing small complexity classes and their theories

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relativizing small complexity classes and their theories
• Space-bounded hierarchies and probabilistic computations
• A measure of relativized space which is faithful with respect to depth
• On uniform circuit complexity
• Separations of theories in weak bounded arithmetic
• On uniformity within \(NC^ 1\)
• A taxonomy of problems with fast parallel algorithms
• RelativizedNC
• Relativization of questions about log space computability
• Theories for TC0 and Other Small Complexity Classes
• Notes on polynomially bounded arithmetic

This page was built for publication: Relativizing small complexity classes and their theories