Počet záznamů: 1

On theories of bounded arithmetic for NC1

SYSNO ASEP	0353280
Druh ASEP	J - Článek v odborném periodiku
Zařazení RIV	J - Článek v odborném periodiku
Poddruh J	Článek ve WOS
Název	On theories of bounded arithmetic for NC1
Tvůrce(i)	Jeřábek, Emil (MU-W)_{RID, SAI, ORCID}
Zdroj.dok.	Annals of Pure and Applied Logic. - : Elsevier - ISSN 0168-0072 Roč. 162, č. 4 (2011), s. 322-340
Poč.str.	19 s.
Jazyk dok.	eng - angličtina
Země vyd.	NL - Nizozemsko
Klíč. slova	bounded arithmetic ; circuit complexity ; propositional translation
Vědní obor RIV	BA - Obecná matematika
CEP	IAA1019401 GA AV ČR - Akademie věd
	1M0545 GA MŠMT - Ministerstvo školství, mládeže a tělovýchovy
CEZ	AV0Z10190503 - MU-W (2005-2011)
UT WOS	000287276800003
EID SCOPUS	78650297477
DOI	10.1016/j.apal.2010.10.001
Anotace	We develop an arithmetical theory VNC1 and its variant VNC1, corresponding to "slightly nonuniform" NC1. Our theories sit between VNC1 and VL, and allow evaluation of log-depth bounded fan-in circuits under limited conditions. Propositional translations of -formulas provable in VNC1 admit L-uniform polynomial-size Frege proofs.
Pracoviště	Matematický ústav
Kontakt	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Rok sběru	2011

Počet záznamů: 1