Propositional representation of arithmetic proofs (Preliminary Version)

DOI10.1145/800133.804354zbMath1282.68112OpenAlexW2122245475MaRDI QIDQ5402564

Martin Dowd

Publication date: 14 March 2014

Published in: Proceedings of the tenth annual ACM symposium on Theory of computing - STOC '78 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/800133.804354

zbMATH Keywords

primitive recursive arithmeticproof systemspropositional calculusNPP

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Towards a unified complexity theory of total functions, Relativized isomorphisms of NP-complete sets, On the complexity of cutting-plane proofs