Number of the records: 1
Incompleteness in the finite domain
- 1.
SYSNO ASEP 0487354 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Incompleteness in the finite domain Author(s) Pudlák, Pavel (MU-W) RID, SAI Source Title Bulletin of Symbolic Logic. - : Cambridge University Press - ISSN 1079-8986
Roč. 23, č. 4 (2017), s. 405-441Number of pages 37 s. Language eng - English Country US - United States Keywords finite domain Subject RIV BA - General Mathematics OECD category Pure mathematics Institutional support MU-W - RVO:67985840 UT WOS 000431007900002 EID SCOPUS 85047437041 DOI 10.1017/bsl.2017.32 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2019
Number of the records: 1