This HTML5 document contains 41 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
n14http://linked.opendata.cz/resource/domain/vavai/projekt/
n12http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n16http://linked.opendata.cz/ontology/domain/vavai/
n10http://linked.opendata.cz/resource/domain/vavai/zamer/
shttp://schema.org/
n5http://linked.opendata.cz/ontology/domain/vavai/riv/
skoshttp://www.w3.org/2004/02/skos/core#
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n18http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F67985840%3A_____%2F08%3A00319585%21RIV09-AV0-67985840/
n7http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n13http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n9http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n6http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n17http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n15http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n8http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F67985840%3A_____%2F08%3A00319585%21RIV09-AV0-67985840
rdf:type
skos:Concept n16:Vysledek
dcterms: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 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. 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.
dcterms:title
Polynomiální a lineární hierarchie v modelech, kde neplatí slabý princip PHP 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
skos:prefLabel
Polynomiální a lineární hierarchie v modelech, kde neplatí slabý princip PHP 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
skos:notation
RIV/67985840:_____/08:00319585!RIV09-AV0-67985840
n5:aktivita
n9:Z n9:P
n5:aktivity
P(LC505), Z(AV0Z10190503)
n5:cisloPeriodika
2
n5:dodaniDat
n8:2009
n5:domaciTvurceVysledku
n12:6610714
n5:druhVysledku
n15:J
n5:duvernostUdaju
n13:S
n5:entitaPredkladatele
n18:predkladatel
n5:idSjednocenehoVysledku
387445
n5:idVysledku
RIV/67985840:_____/08:00319585
n5:jazykVysledku
n6:eng
n5:klicovaSlova
polynomial and linear hierarchies in models
n5:klicoveSlovo
n7:polynomial%20and%20linear%20hierarchies%20in%20models
n5:kodStatuVydavatele
US - Spojené státy americké
n5:kontrolniKodProRIV
[7B12CBE9FDC1]
n5:nazevZdroje
Journal of Symbolic Logic
n5:obor
n17:BA
n5:pocetDomacichTvurcuVysledku
1
n5:pocetTvurcuVysledku
2
n5:projekt
n14:LC505
n5:rokUplatneniVysledku
n8:2008
n5:svazekPeriodika
73
n5:tvurceVysledku
Thapen, Neil Kolodziejczyk, L.. A.
n5:wos
000256103700013
n5:zamer
n10:AV0Z10190503
s:issn
0022-4812
s:numberOfPages
15