Incompleteness in the finite domain
From MaRDI portal
Abstract: Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyond . These conjectures formally connect computational complexity with the difficulty of proving some sentences, which means that high computational complexity of a problem associated with a sentence implies that the sentence is not provable in a weak theory, or requires a long proof. Another reason for putting forward these conjectures is that some results in proof complexity seem to be special cases of such general statements and we want to formalize and fully understand these statements. In this paper we review some conjectures that we have presented earlier, introduce new conjectures, systematize them and prove new connections between them and some other statements studied before.
Recommendations
- Further oracles separating conjectures about incompleteness in the finite domain
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Complexity classes as mathematical axioms
- Infinite versions of some problems from finite complexity theory
- An oracle separating conjectures about incompleteness in the finite domain
Cites work
- A note on bounded arithmetic
- A Note on Conservativity Relations among Bounded Arithmetic Theories
- Abbreviating proofs by adding new axioms
- Alternating minima and maxima, Nash equilibria and bounded arithmetic
- Bounded arithmetic and the polynomial hierarchy
- Canonical disjoint NP-pairs of propositional proof systems
- Characterising definable search problems in bounded arithmetic via proof notations
- Disjoint NP-Pairs
- Fragments of approximate counting
- Herbrandizing search problems in Bounded Arithmetic
- How easy is local search?
- scientific article; zbMATH DE number 4004177 (Why is no real title available?)
- scientific article; zbMATH DE number 4033740 (Why is no real title available?)
- scientific article; zbMATH DE number 4059391 (Why is no real title available?)
- scientific article; zbMATH DE number 3557241 (Why is no real title available?)
- scientific article; zbMATH DE number 1215493 (Why is no real title available?)
- scientific article; zbMATH DE number 819737 (Why is no real title available?)
- scientific article; zbMATH DE number 227056 (Why is no real title available?)
- Improved witnessing and local improvement principles for second-order bounded arithmetic
- Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
- Logical foundations of mathematics and computational complexity. A gentle introduction
- Nondeterministic functions and the existence of optimal proof systems
- On the complexity of k-SAT
- On the complexity of finding falsifying assignments for Herbrand disjunctions
- On the computational content of intuitionistic propositional proofs
- ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
- Optimal proof systems imply complete sets for promise classes
- Parity Games and Propositional Proofs
- Polynomial local search in the polynomial hierarchy and witnessing in fragments of bounded arithmetic
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
- The complexity of the disjunction and existential properties in intuitionistic logic
- The provably total NP search problems of weak second order bounded arithmetic
- The provably total search problems of bounded arithmetic
- The relative efficiency of propositional proof systems
Cited in
(19)- Some impossibility results with domain restrictions
- Infinite versions of some problems from finite complexity theory
- Is there a simple, pedestrian arithmetic sentence which is independent of ZFC?
- Incompleteness and the Barcan formula
- On the proof complexity of logics of bounded branching
- Short proofs for slow consistency
- Further oracles separating conjectures about incompleteness in the finite domain
- An oracle separating conjectures about incompleteness in the finite domain
- Typical forcings, NP search problems and an extension of a theorem of Riis
- Incompleteness and fixed points
- scientific article; zbMATH DE number 3979054 (Why is no real title available?)
- scientific article; zbMATH DE number 1062120 (Why is no real title available?)
- 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
- NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
- The consistency of arithmetic
- Consistent ultrafinitist logic
- An oracle with no up-complete sets, but NP = PSPACE
- Complexity classes as mathematical axioms
This page was built for publication: Incompleteness in the finite domain
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4640304)
