INCOMPLETENESS IN THE FINITE DOMAIN

DOI10.1017/bsl.2017.32zbMath1423.03245arXiv1601.01487OpenAlexW2963187611MaRDI QIDQ4640304

Pavel Pudlák

Publication date: 17 May 2018

Published in: The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1601.01487

zbMATH Keywords

propositional proof systemssearch problemsdisjoint NP-setsfinite consistency

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Gödel numberings and issues of incompleteness (03F40)

Related Items (9)

Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ Short proofs for slow consistency ⋮ NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Further oracles separating conjectures about incompleteness in the finite domain ⋮ The consistency of arithmetic ⋮ An oracle separating conjectures about incompleteness in the finite domain ⋮ CURRENT RESEARCH ON GÖDEL’S INCOMPLETENESS THEOREMS ⋮ P-Optimal Proof Systems for Each NP-Set but no Complete Disjoint NP-Pairs Relative to an Oracle ⋮ On the proof complexity of logics of bounded branching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The provably total NP search problems of weak second order bounded arithmetic
• Alternating minima and maxima, Nash equilibria and bounded arithmetic
• Nondeterministic functions and the existence of optimal proof systems
• Canonical disjoint NP-pairs of propositional proof systems
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• How easy is local search?
• Bounded arithmetic and the polynomial hierarchy
• The complexity of the disjunction and existential properties in intuitionistic logic
• Optimal proof systems imply complete sets for promise classes
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• FRAGMENTS OF APPROXIMATE COUNTING
• The provably total search problems of bounded arithmetic
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• Herbrandizing search problems in Bounded Arithmetic
• A note on bounded arithmetic
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• POLYNOMIAL LOCAL SEARCH IN THE POLYNOMIAL HIERARCHY AND WITNESSING IN FRAGMENTS OF BOUNDED ARITHMETIC
• The relative efficiency of propositional proof systems
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• A Note on Conservativity Relations among Bounded Arithmetic Theories
• Disjoint NP-Pairs
• Logical Foundations of Mathematics and Computational Complexity
• Parity Games and Propositional Proofs
• Improved witnessing and local improvement principles for second-order bounded arithmetic
• Abbreviating proofs by adding new axioms
• On the computational content of intuitionistic propositional proofs
• On the complexity of \(k\)-SAT

This page was built for publication: INCOMPLETENESS IN THE FINITE DOMAIN