Logical foundations of mathematics and computational complexity. A gentle introduction

DOI10.1007/978-3-319-00119-7MaRDI QIDQ4913583zbMATH OpenOpenAlexWikidataFDO

Authors Pavel Pudlák

Publication date 8 April 2013

Published in Springer Monographs in Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-00119-7

zbMATH Keywords

computational complexityconsistencyexistencefoundations of mathematicstruthcomputationlogicproof complexityset theorylanguageproofs of impossibility

Mathematics Subject Classification ID

Proof theory in general (including proof-theoretic semantics) (03F03) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Consistency and independence results (03E35) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Gödel numberings and issues of incompleteness (03F40) Complexity of computation (including implicit computational complexity) (03D15) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Axiomatics of classical set theory and its fragments (03E30)

Recommendations

• scientific article; zbMATH DE number 3948222
• scientific article; zbMATH DE number 2232435
• The foundations of mathematics
• scientific article; zbMATH DE number 2150901
• There's something about Gödel. The complete guide to the incompleteness theorem. Transl. from the Italian

Cited in

(20)

• Generic properties of a computational task predict human effort and performance
• Further oracles separating conjectures about incompleteness in the finite domain
• An oracle separating conjectures about incompleteness in the finite domain
• scientific article; zbMATH DE number 2134000 (Why is no real title available?)
• P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle
• Gödel, Tarski and the lure of natural language. Logical entanglement, formalism freeness
• scientific article; zbMATH DE number 5072506 (Why is no real title available?)
• Incompleteness in the finite domain
• scientific article; zbMATH DE number 4075014 (Why is no real title available?)
• Complexity barriers as independence
• scientific article; zbMATH DE number 1344905 (Why is no real title available?)
• Typical forcings, NP search problems and an extension of a theorem of Riis
• The Gödel phenomenon in mathematics: a modern view
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• Polynomial time ultrapowers and the consistency of circuit lower bounds
• Computation, logic, games, and quantum foundations. The many facets of Samson Abramsky. Essays dedicated to Samson Abramsky on the occasion of his 60th birthday
• NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
• Martin Davis on computability, computational logic, and mathematical foundations
• Truth and speed-up
• The foundational debate. Complexity and constructivity in mathematics and physics. Proceedings of the conference on the foundational debate: constructivity and complexity in logic, mathematics and physics, Vienna, Austria, September 1994

This page was built for publication: Logical foundations of mathematics and computational complexity. A gentle introduction

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