Number of the records: 1

On theories of bounded arithmetic for NC1

SYSNO ASEP	0353280
Document Type	J - Journal Article
R&D Document Type	Journal Article
Subsidiary J	Článek ve WOS
Title	On theories of bounded arithmetic for NC1
Author(s)	Jeřábek, Emil (MU-W)_{RID, SAI, ORCID}
Source Title	Annals of Pure and Applied Logic. - : Elsevier - ISSN 0168-0072 Roč. 162, č. 4 (2011), s. 322-340
Number of pages	19 s.
Language	eng - English
Country	NL - Netherlands
Keywords	bounded arithmetic ; circuit complexity ; propositional translation
Subject RIV	BA - General Mathematics
R&D Projects	IAA1019401 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR)
	1M0545 GA MŠMT - Ministry of Education, Youth and Sports (MEYS)
CEZ	AV0Z10190503 - MU-W (2005-2011)
UT WOS	000287276800003
EID SCOPUS	78650297477
DOI	10.1016/j.apal.2010.10.001
Annotation	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.
Workplace	Mathematical Institute
Contact	Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757
Year of Publishing	2011

Number of the records: 1