Počet záznamů: 1
Incompleteness in the finite domain
- 1.
SYSNO ASEP 0487354 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Incompleteness in the finite domain Tvůrce(i) Pudlák, Pavel (MU-W) RID, SAI Zdroj.dok. Bulletin of Symbolic Logic. - : Cambridge University Press - ISSN 1079-8986
Roč. 23, č. 4 (2017), s. 405-441Poč.str. 37 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova finite domain Vědní obor RIV BA - Obecná matematika Obor OECD Pure mathematics Institucionální podpora MU-W - RVO:67985840 UT WOS 000431007900002 EID SCOPUS 85047437041 DOI 10.1017/bsl.2017.32 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2019
Počet záznamů: 1