Logical Foundations of Mathematics and Computational Complexity

DOI10.1007/978-3-319-00119-7zbMath1270.03001OpenAlexW2487337578WikidataQ55121571 ScholiaQ55121571MaRDI QIDQ4913583

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 complexityexistenceconsistencytruthlanguageset theorylogiccomputationfoundations of mathematicsproof complexityproofs of impossibility

Mathematics Subject Classification ID

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

Related Items (10)

Generic properties of a computational task predict human effort and performance ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ TRUTH AND SPEED-UP ⋮ NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ On the complexity of finding falsifying assignments for Herbrand disjunctions ⋮ Further oracles separating conjectures about incompleteness in the finite domain ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ An oracle separating conjectures about incompleteness in the finite domain ⋮ P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle

This page was built for publication: Logical Foundations of Mathematics and Computational Complexity