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 条

[41] Open induction in a bounded arithmetic for TC0
Emil Jeřábek
[J]. Archive for Mathematical Logic, 2015, 54 : 359 - 394
[42] An independence result on weak second order bounded arithmetic
Kuroda, S
[J]. MATHEMATICAL LOGIC QUARTERLY, 2001, 47 (02) : 183 - 186
[43] Feasible operations on proofs: The logic of proofs for bounded arithmetic
Goris, Evan
[J]. THEORY OF COMPUTING SYSTEMS, 2008, 43 (02) : 185 - 203
[44] Existentially Closed Models and Conservation Results in Bounded Arithmetic
Cordon-Franco, A.
Fernandez-Margarit, A.
Lara-Martin, F. F.
[J]. JOURNAL OF LOGIC AND COMPUTATION, 2009, 19 (01) : 123 - 143
[45] Alternating minima and maxima, Nash equilibria and Bounded Arithmetic
Pudlak, Pavel
Thapen, Neil
[J]. ANNALS OF PURE AND APPLIED LOGIC, 2012, 163 (05) : 604 - 614
[46] Preservation theorems and restricted consistency statements in bounded arithmetic
Beckmann, A
[J]. ANNALS OF PURE AND APPLIED LOGIC, 2004, 126 (1-3) : 255 - 280
[47] CONSISTENCY PROOF OF A FRAGMENT OF PV WITH SUBSTITUTION IN BOUNDED ARITHMETIC
Yamagata, Yoriyuki
[J]. JOURNAL OF SYMBOLIC LOGIC, 2018, 83 (03) : 1063 - 1090
[48] Bounded arithmetic, proof complexity and two papers of Parikh
Buss, SR
[J]. ANNALS OF PURE AND APPLIED LOGIC, 1999, 96 (1-3) : 43 - 55
[49] Construction of models of bounded arithmetic by restricted reduced powers
Garlik, Michal
[J]. ARCHIVE FOR MATHEMATICAL LOGIC, 2016, 55 (5-6) : 625 - 648
[50] Feasible Operations on Proofs: The Logic of Proofs for Bounded Arithmetic
Evan Goris
[J]. Theory of Computing Systems, 2008, 43 : 185 - 203

← 1 2 3 4 5 →