About: The provably total search problems of bounded arithmetic

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: The provably total search problems of bounded arithmetic Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
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. (en)
Title	The provably total search problems of bounded arithmetic The provably total search problems of bounded arithmetic (en)
skos:prefLabel	The provably total search problems of bounded arithmetic The provably total search problems of bounded arithmetic (en)
skos:notation	RIV/67985840:_____/11:00369680!RIV12-AV0-67985840
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(LC505), Z(AV0Z10190503)
http://linked.open...iv/cisloPeriodika	1
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Thapen, Neil
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Matematický ústav AV ČR, v. v. i.
http://linked.open...dnocenehoVysledku	224926
http://linked.open...ai/riv/idVysledku	RIV/67985840:_____/11:00369680
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Pigeonhole principle; polynomial hierarchy; local search (en)
http://linked.open.../riv/klicoveSlovo	local search Pigeonhole principle polynomial hierarchy
http://linked.open...odStatuVydavatele	GB - Spojené království Velké Británie a Severního Irska
http://linked.open...ontrolniKodProRIV	[AE30141C4A16]
http://linked.open...i/riv/nazevZdroje	Proceedings of the London Mathematical Society
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Eduard Čech Center for Algebra and Geometry
http://linked.open...UplatneniVysledku	2011
http://linked.open...v/svazekPeriodika	103
http://linked.open...iv/tvurceVysledku	Thapen, Neil Skelley, A.
http://linked.open...ain/vavai/riv/wos	000292311700004
http://linked.open...n/vavai/riv/zamer	Rozvoj a prohloubení obecných matematických poznatků a jejich užití v dalších vědních oborech a v praxi
issn	0024-6115
number of pages	33 (xsd:int)
http://bibframe.org/vocab/doi	10.1112/plms/pdq044

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 77 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software