This HTML5 document contains 42 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/
n13http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n9http://linked.opendata.cz/resource/domain/vavai/projekt/
n8http://linked.opendata.cz/resource/domain/vavai/subjekt/
n7http://linked.opendata.cz/ontology/domain/vavai/
n19http://linked.opendata.cz/resource/domain/vavai/zamer/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n3http://linked.opendata.cz/ontology/domain/vavai/riv/
n20http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F67985840%3A_____%2F11%3A00369680%21RIV12-AV0-67985840/
n18http://bibframe.org/vocab/
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n4http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n16http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n11http://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/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n15http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F67985840%3A_____%2F11%3A00369680%21RIV12-AV0-67985840
rdf:type
n7:Vysledek skos:Concept
dcterms:description
We give combinatorial principles GI(k), based on k-turn games, which are complete for the class of NP search problems provably total at the kth level T(2)(k) of the bounded arithmetic hierarchy and hence characterize the for all Sigma(b)(1) consequences of T(2)(k). Our argument uses a translation of first-order proofs into large, uniform propositional proofs in a system in which the soundness of the rules can be witnessed by polynomial time reductions between games. We show that for all(Sigma) over cap (b)(1)(alpha) conservativity of T(2)(i+1) (alpha) over T(2)(i)(alpha) already implies. for all(Sigma) over cap (b)(1)(a) conservativity of T(2)(alpha) over T(2)(i)(alpha). We translate this into propositional form and give a polylogarithmic width CNF (GI(3)) over bar such that if (GI(3)) over bar has small R(log) refutations then so does any polylogarithmic width CNF which has small constant depth refutations. We prove a resolution lower bound for (GI(3)) over bar. We give combinatorial principles GI(k), based on k-turn games, which are complete for the class of NP search problems provably total at the kth level T(2)(k) of the bounded arithmetic hierarchy and hence characterize the for all Sigma(b)(1) consequences of T(2)(k). Our argument uses a translation of first-order proofs into large, uniform propositional proofs in a system in which the soundness of the rules can be witnessed by polynomial time reductions between games. We show that for all(Sigma) over cap (b)(1)(alpha) conservativity of T(2)(i+1) (alpha) over T(2)(i)(alpha) already implies. for all(Sigma) over cap (b)(1)(a) conservativity of T(2)(alpha) over T(2)(i)(alpha). We translate this into propositional form and give a polylogarithmic width CNF (GI(3)) over bar such that if (GI(3)) over bar has small R(log) refutations then so does any polylogarithmic width CNF which has small constant depth refutations. We prove a resolution lower bound for (GI(3)) over bar.
dcterms:title
The provably total search problems of bounded arithmetic The provably total search problems of bounded arithmetic
skos:prefLabel
The provably total search problems of bounded arithmetic The provably total search problems of bounded arithmetic
skos:notation
RIV/67985840:_____/11:00369680!RIV12-AV0-67985840
n7:predkladatel
n8:ico%3A67985840
n3:aktivita
n11:P n11:Z
n3:aktivity
P(LC505), Z(AV0Z10190503)
n3:cisloPeriodika
1
n3:dodaniDat
n15:2012
n3:domaciTvurceVysledku
n13:6610714
n3:druhVysledku
n12:J
n3:duvernostUdaju
n16:S
n3:entitaPredkladatele
n20:predkladatel
n3:idSjednocenehoVysledku
224926
n3:idVysledku
RIV/67985840:_____/11:00369680
n3:jazykVysledku
n6:eng
n3:klicovaSlova
Pigeonhole principle; polynomial hierarchy; local search
n3:klicoveSlovo
n4:Pigeonhole%20principle n4:polynomial%20hierarchy n4:local%20search
n3:kodStatuVydavatele
GB - Spojené království Velké Británie a Severního Irska
n3:kontrolniKodProRIV
[AE30141C4A16]
n3:nazevZdroje
Proceedings of the London Mathematical Society
n3:obor
n17:BA
n3:pocetDomacichTvurcuVysledku
1
n3:pocetTvurcuVysledku
2
n3:projekt
n9:LC505
n3:rokUplatneniVysledku
n15:2011
n3:svazekPeriodika
103
n3:tvurceVysledku
Skelley, A. Thapen, Neil
n3:wos
000292311700004
n3:zamer
n19:AV0Z10190503
s:issn
0024-6115
s:numberOfPages
33
n18:doi
10.1112/plms/pdq044