New relations and separations of conjectures about incompleteness in the finite domain
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F22%3A00561027" target="_blank" >RIV/67985840:_____/22:00561027 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1017/jsl.2021.99" target="_blank" >https://doi.org/10.1017/jsl.2021.99</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1017/jsl.2021.99" target="_blank" >10.1017/jsl.2021.99</a>
Alternative languages
Result language
angličtina
Original language name
New relations and separations of conjectures about incompleteness in the finite domain
Original language description
In [20] Krajíček and Pudlák discovered connections between problems in computational complexity and the lengths of first-order proofs of finite consistency statements. Later Pudlák [25] studied more statements that connect provability with computational complexity and conjectured that they are true. All these conjectures are at least as strong as [23-25].One of the problems concerning these conjectures is to find out how tightly they are connected with statements about computational complexity classes. Results of this kind had been proved in [20, 22].In this paper, we generalize and strengthen these results. Another question that we address concerns the dependence between these conjectures. We construct two oracles that enable us to answer questions about relativized separations asked in [19, 25] (i.e., for the pairs of conjectures mentioned in the questions, we construct oracles such that one conjecture from the pair is true in the relativized world and the other is false and vice versa). We also show several new connections between the studied conjectures. In particular, we show that the relation between the finite reflection principle and proof systems for existentially quantified Boolean formulas is similar to the one for finite consistency statements and proof systems for non-quantified propositional tautologies.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2022
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Journal of Symbolic Logic
ISSN
0022-4812
e-ISSN
1943-5886
Volume of the periodical
87
Issue of the periodical within the volume
3
Country of publishing house
US - UNITED STATES
Number of pages
26
Pages from-to
912-937
UT code for WoS article
000847361900005
EID of the result in the Scopus database
2-s2.0-85120650154