Propositional representation of arithmetic proofs (preliminary version)

DOI10.1145/800133.804354MaRDI QIDQ5402564zbMATH OpenOpenAlexFDO

Authors 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

proof systemsNPprimitive recursive arithmeticPpropositional calculus

Mathematics Subject Classification ID

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

Recommendations

• An arithmetic for non-size-increasing polynomial-time computation
• scientific article; zbMATH DE number 3860379
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• scientific article; zbMATH DE number 1114022
• scientific article; zbMATH DE number 1059248

Cited in

(8)

• Towards a unified complexity theory of total functions
• On the complexity of cutting-plane proofs
• scientific article; zbMATH DE number 3900723 (Why is no real title available?)
• From arithmetic expressions to propositional formulae
• Producing proofs from an arithmetic decision procedure in elliptical LF
• scientific article; zbMATH DE number 3860379 (Why is no real title available?)
• scientific article; zbMATH DE number 3859101 (Why is no real title available?)
• Relativized isomorphisms of NP-complete sets

This page was built for publication: Propositional representation of arithmetic proofs (preliminary version)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5402564)