Incompleteness in the finite domain

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F17%3A00487354" target="_blank" >RIV/67985840:_____/17:00487354 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1017/bsl.2017.32" target="_blank" >http://dx.doi.org/10.1017/bsl.2017.32</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1017/bsl.2017.32" target="_blank" >10.1017/bsl.2017.32</a>

Result language
angličtina
Original language name
Incompleteness in the finite domain
Original language description
Motivated by the problem of finding finite versions of classical incompleteness theorems, we present some conjectures that go beyond NP coNP. 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. Roughly speaking, we are trying to connect syntactic complexity, by which we mean the complexity of sentences and strengths of the theories in which they are provable, with the semantic concept of complexity of the computational problems represented by these sentences.
Czech name
—
Czech description
—

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

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2017
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)