Incompleteness in the finite domain

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Incompleteness in the finite domain

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Incompleteness in the finite domain

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

Kód důvěrnosti údajů

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

Název periodika

Bulletin of Symbolic Logic

ISSN

1079-8986

e-ISSN

—

Svazek periodika

23

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

37

Strana od-do

405-441

Kód UT WoS článku

000431007900002

EID výsledku v databázi Scopus

2-s2.0-85047437041