Attributes | Values |
---|
rdf:type
| |
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. (cs)
- 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 not collapse 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.
- 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 not collapse 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. (en)
|
Title
| - The polynomial and linear hierarchies in models where the weak pigeonhole principle fails
- The polynomial and linear hierarchies in models where the weak pigeonhole principle fails (en)
- Polynomiální a lineární hierarchie v modelech, kde neplatí slabý princip PHP (cs)
|
skos:prefLabel
| - The polynomial and linear hierarchies in models where the weak pigeonhole principle fails
- The polynomial and linear hierarchies in models where the weak pigeonhole principle fails (en)
- Polynomiální a lineární hierarchie v modelech, kde neplatí slabý princip PHP (cs)
|
skos:notation
| - RIV/67985840:_____/08:00319585!RIV09-AV0-67985840
|
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| - P(LC505), Z(AV0Z10190503)
|
http://linked.open...iv/cisloPeriodika
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/67985840:_____/08:00319585
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - polynomial and linear hierarchies in models (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...odStatuVydavatele
| - US - Spojené státy americké
|
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...i/riv/nazevZdroje
| - Journal of Symbolic Logic
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...v/svazekPeriodika
| |
http://linked.open...iv/tvurceVysledku
| - Thapen, Neil
- Kolodziejczyk, L.. A.
|
http://linked.open...ain/vavai/riv/wos
| |
http://linked.open...n/vavai/riv/zamer
| |
issn
| |
number of pages
| |