On theories of bounded arithmetic for NC1

被引：5

作者：

Jerabek, Emil ^{[1
]}

机构：

[1] Acad Sci Czech Republ, Inst Math, CR-11567 Prague 1, Czech Republic

来源：

ANNALS OF PURE AND APPLIED LOGIC | 2011年 / 162卷 / 04期

关键词：

Bounded arithmetic; Circuit complexity; Propositional translation;

D O I：

10.1016/j.apal.2010.10.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We develop an arithmetical theory VNC*1 and its variant (VNC) over bar (1)(*), 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 Sigma(B)(0)(L-(VNC*1) over bar)-formulas provable in L (VNC) over bar (1)(*) admit L-uniform polynomial-size Frege proofs. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：322 / 340

页数：19

共 50 条

[1] ON PROVING CONSISTENCY OF EQUATIONAL THEORIES IN BOUNDED ARITHMETIC
Beckmann, Arnold
Yamagata, Yoriyuki
JOURNAL OF SYMBOLIC LOGIC, 2025,
[2] Structure and definability in general bounded arithmetic theories
Pollett, C
ANNALS OF PURE AND APPLIED LOGIC, 1999, 100 (1-3) : 189 - 245
[3] Correlation Bounds Against Monotone NC1
Rossman, Benjamin
30TH CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC 2015), 2015, 33 : 392 - 411
[4] Separations of first and second order theories in bounded arithmetic
Yasumoto, M
ARCHIVE FOR MATHEMATICAL LOGIC, 2005, 44 (06) : 685 - 688
[5] Separations of first and second order theories in bounded arithmetic
Masahiro Yasumoto
Archive for Mathematical Logic, 2005, 44 : 685 - 688
[6] A note on conservativity relations among bounded arithmetic theories
Impagliazzo, R
Krajícek, J
MATHEMATICAL LOGIC QUARTERLY, 2002, 48 (03) : 375 - 377
[7] MODELS OF BOUNDED ARITHMETIC THEORIES AND SOME RELATED COMPLEXITY QUESTIONS
Alam, Abolfazl
Moniri, Morteza
BULLETIN OF THE SECTION OF LOGIC, 2022, 51 (02): : 163 - 176
[8] Quantified propositional calculus and a second-order theory for NC1
Cook, S
Morioka, T
ARCHIVE FOR MATHEMATICAL LOGIC, 2005, 44 (06) : 711 - 749
[9] Quantified propositional calculus and a second-order theory for NC1
Stephen Cook
Tsuyoshi Morioka
Archive for Mathematical Logic, 2005, 44 : 711 - 749
[10] A sorting network in bounded arithmetic
Jerabek, Emil
ANNALS OF PURE AND APPLIED LOGIC, 2011, 162 (04) : 341 - 355

← 1 2 3 4 5 →