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

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

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

Original language description

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.

Czech name

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

Czech description

Dokázali jsme několik podmíněných výsledků o nedokazatelnosti vět ze strukturální teorie složitosti a slabé aritmetiky. Konkrétně jsme ukázali za předpokladu, že rozklad čísel je těžká operace, že existuje model PV, ve kterém polynomiální hierarchie nekolapsuje na lineární hierarchii, že existuje model S^1_2, ve kterém NP není druhá hladina lineární hierarchie a že existuje model S^1_2, ve kterém polynomiální hierarchie kolapsuje na lineární hierarchii.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/LC505" target="_blank" >LC505: Eduard Čech Center for Algebra and Geometry</a><br>

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2008

Confidentiality

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

Name of the periodical

Journal of Symbolic Logic

ISSN

0022-4812

e-ISSN

—

Volume of the periodical

73

Issue of the periodical within the volume

2

Country of publishing house

US - UNITED STATES

Number of pages

15

Pages from-to

—

UT code for WoS article

000256103700013

EID of the result in the Scopus database

—