Polynomiální a lineární hierarchie v modelech, kde neplatí slabý princip PHP

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F08%3A00319585" target="_blank" >RIV/67985840:_____/08:00319585 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

The polynomial and linear hierarchies in models where the weak pigeonhole principle fails

Popis výsledku v původním jazyce

We give some conditional unprovability results about statements from structural complexity theory in weak arithmetic. In particular we show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does notcollapse to the linear hierarchy; that a model of S^1_2 exists in which NP is not in the second level of the linear hierarchy; and that a model of S^1_2 exists in which the polynomial hierarchy collapses to the linear hierarchy and in which the strict version of PH does not collapse to a finite level.

Název v anglickém jazyce

The polynomial and linear hierarchies in models where the weak pigeonhole principle fails

Popis výsledku anglicky

We give some conditional unprovability results about statements from structural complexity theory in weak arithmetic. In particular we show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does notcollapse to the linear hierarchy; that a model of S^1_2 exists in which NP is not in the second level of the linear hierarchy; and that a model of S^1_2 exists in which the polynomial hierarchy collapses to the linear hierarchy and in which the strict version of PH does not collapse to a finite level.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/LC505" target="_blank" >LC505: Centrum Eduarda Čecha pro algebru a geometrii</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

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

Journal of Symbolic Logic

ISSN

0022-4812

e-ISSN

—

Svazek periodika

73

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

15

Strana od-do

—

Kód UT WoS článku

000256103700013

EID výsledku v databázi Scopus

—