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 条

[31] End extensions of models of linearly bounded arithmetic
Zambella, D
ANNALS OF PURE AND APPLIED LOGIC, 1997, 88 (2-3) : 263 - 277
[32] On rules and parameter free systems in bounded arithmetic
Cordon-Franco, A.
Fernandez-Margarit, A.
Lara-Martin, F. F.
COMPUTATION AND LOGIC IN THE REAL WORLD, PROCEEDINGS, 2007, 4497 : 179 - +
[33] Sprague-Grundy theory in bounded arithmetic
Kuroda, Satoru
ARCHIVE FOR MATHEMATICAL LOGIC, 2022, 61 (1-2) : 233 - 262
[34] Cuts and overspill properties in models of bounded arithmetic
Moniri, Morteza
Sajjadi, S. Hosein
IRANIAN JOURNAL OF MATHEMATICAL SCIENCES AND INFORMATICS, 2013, 8 (01): : 59 - 66
[35] Third-order computation and bounded arithmetic
Skelley, Alan
JOURNAL OF LOGIC AND COMPUTATION, 2007, 17 (06) : 1167 - 1191
[36] Indistinguishability Obfuscation, Range Avoidance, and Bounded Arithmetic
Ilango, Rahul
Li, Jiatu
Williams, R. Ryan
PROCEEDINGS OF THE 55TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, STOC 2023, 2023, : 1076 - 1089
[37] An unexpected separation result in Linearly Bounded Arithmetic
Beckmann, A
Johannsen, J
MATHEMATICAL LOGIC QUARTERLY, 2005, 51 (02) : 191 - 200
[38] A remark on independence results for sharply bounded arithmetic
Johannsen, J
MATHEMATICAL LOGIC QUARTERLY, 1998, 44 (04) : 568 - 570
[39] Upper and lower Ramsey bounds in bounded arithmetic
Ojakian, K
ANNALS OF PURE AND APPLIED LOGIC, 2005, 135 (1-3) : 135 - 150
[40] Open induction in a bounded arithmetic for TC0
Jerabek, Emil
ARCHIVE FOR MATHEMATICAL LOGIC, 2015, 54 (3-4) : 359 - 394

← 1 2 3 4 5 →