About: The provably total NP search problems of weak second order bounded arithmetic

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

About: The provably total NP search problems of weak second order 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 define a new NP search problem, the %22local improvement%22 principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in PV, it characterizes the for all Sigma(b)(1) consequences of V-2(1) and that natural restrictions of it characterize the for all Sigma(b)(1) consequences of U-2(1) and of the bounded arithmetic hierarchy. We also show that over V-0 it characterizes the for all Sigma(B)(0) consequences of V-1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the for all Pi(b)(1) consequences of S-2(1). Throughout our search problems are %22type-2%22 NP search problems, which take second-order objects as parameters: (c) 2011 Elsevier B.V. All rights reserved. We define a new NP search problem, the %22local improvement%22 principle, about labellings of an acyclic, bounded-degree graph. We show that, provably in PV, it characterizes the for all Sigma(b)(1) consequences of V-2(1) and that natural restrictions of it characterize the for all Sigma(b)(1) consequences of U-2(1) and of the bounded arithmetic hierarchy. We also show that over V-0 it characterizes the for all Sigma(B)(0) consequences of V-1 and hence that, in some sense, a miniaturized version of the principle gives a new characterization of the for all Pi(b)(1) consequences of S-2(1). Throughout our search problems are %22type-2%22 NP search problems, which take second-order objects as parameters: (c) 2011 Elsevier B.V. All rights reserved. (en)
Title	The provably total NP search problems of weak second order bounded arithmetic The provably total NP search problems of weak second order bounded arithmetic (en)
skos:prefLabel	The provably total NP search problems of weak second order bounded arithmetic The provably total NP search problems of weak second order bounded arithmetic (en)
skos:notation	RIV/67985840:_____/11:00359552!RIV12-AV0-67985840
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(IAA100190902), P(LC505), Z(AV0Z10190503)
http://linked.open...iv/cisloPeriodika	6
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Thapen, Neil Nguyen, Phuong
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	224925
http://linked.open...ai/riv/idVysledku	RIV/67985840:_____/11:00359552
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	complexity; fragments (en)
http://linked.open.../riv/klicoveSlovo	complexity fragments
http://linked.open...odStatuVydavatele	NL - Nizozemsko
http://linked.open...ontrolniKodProRIV	[9E27C181F804]
http://linked.open...i/riv/nazevZdroje	Annals of Pure and Applied Logic
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Eduard Čech Center for Algebra and Geometry Mathematical logic, complexity, and algorithms
http://linked.open...UplatneniVysledku	2011
http://linked.open...v/svazekPeriodika	162
http://linked.open...iv/tvurceVysledku	Thapen, Neil Kolodziejczyk, L.. A. Nguyen, Phuong
http://linked.open...ain/vavai/riv/wos	000289022500002
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	0168-0072
number of pages	28 (xsd:int)
http://bibframe.org/vocab/doi	10.1016/j.apal.2010.12.002

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