NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
DOI10.1017/jsl.2021.99OpenAlexW3215216929WikidataQ122931547 ScholiaQ122931547MaRDI QIDQ5100043
Publication date: 29 August 2022
Published in: The Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.01362
propositional proof systemsoraclesfinite consistency\textsf{TFNP} classdisjoint NE-setsrelativized worlds
Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20) Gödel numberings and issues of incompleteness (03F40)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of finding falsifying assignments for Herbrand disjunctions
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- The complexity of the pigeonhole principle
- Count\((q)\) versus the pigeon-hole principle
- An oracle builder's toolkit
- Inverting onto functions.
- Expander construction in \(\mathrm{VNC}^1\)
- Does the polynomial hierarchy collapse if onto functions are invertible?
- An oracle separating conjectures about incompleteness in the finite domain
- Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- On p-Optimal Proof Systems and Logics for PTIME
- Sparse Sets in : Relativizations
- The relative efficiency of propositional proof systems
- Proof Complexity
- INCOMPLETENESS IN THE FINITE DOMAIN
- Disjoint NP-Pairs
- Logical Foundations of Mathematics and Computational Complexity
This page was built for publication: NEW RELATIONS AND SEPARATIONS OF CONJECTURES ABOUT INCOMPLETENESS IN THE FINITE DOMAIN
