Počet záznamů: 1  

Incompleteness in the finite domain

  1. 1.
    0487354 - MÚ 2019 RIV US eng J - Článek v odborném periodiku
    Pudlák, Pavel
    Incompleteness in the finite domain.
    Bulletin of Symbolic Logic. Roč. 23, č. 4 (2017), s. 405-441. ISSN 1079-8986. E-ISSN 1943-5894
    GRANT EU: European Commission(XE) 339691 - FEALORA
    Institucionální podpora: RVO:67985840
    Klíčová slova: finite domain
    Obor OECD: Pure mathematics
    Impakt faktor: 0.613, rok: 2017
    https://www.cambridge.org/core/journals/bulletin-of-symbolic-logic/article/incompleteness-in-the-finite-domain/D239B1761A73DCA534A4805A76D81C76

    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.
    Trvalý link: http://hdl.handle.net/11104/0282020

     
    Název souboruStaženoVelikostKomentářVerzePřístup
    Pudlak4.pdf8623 KBVydavatelský postprintvyžádat
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.