Unprovability of theorems of complexity theory in weak number theories

DOI10.1016/0304-3975(82)90068-8zbMath0482.03025OpenAlexW2011569379WikidataQ126590587 ScholiaQ126590587MaRDI QIDQ1162506

Daniel Leivant

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90068-8

zbMATH Keywords

proof theoryformal theoriesexistence of recursive sets that are almost everywhere difficult to decideindependence of Rabin's theorem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity of proofs (03F20)

Related Items

How to prove representation-independent independence results, Index sets and presentations of complexity classes, Polynomial time computations in models of ET

Cites Work

• The optimality of induction as an axiomatization of arithmetic
• The Expressiveness of Simple and Second-Order Type Structures
• On the Computational Complexity of Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item