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 条

[21] Partially definable forcing and bounded arithmetic
Albert Atserias
Moritz Müller
Archive for Mathematical Logic, 2015, 54 : 1 - 33
[22] Herbrandizing search problems in Bounded Arithmetic
Hanika, J
MATHEMATICAL LOGIC QUARTERLY, 2004, 50 (06) : 577 - 586
[23] A bounded arithmetic AID for Frege systems
Arai, T
ANNALS OF PURE AND APPLIED LOGIC, 2000, 103 (1-3) : 155 - 199
[24] Lifting independence results in bounded arithmetic
Mario Chiari
Jan Krajíček
Archive for Mathematical Logic, 1999, 38 : 123 - 138
[25] Lifting independence results in bounded arithmetic
Chiari, M
Krajicek, J
ARCHIVE FOR MATHEMATICAL LOGIC, 1999, 38 (02) : 123 - 138
[26] Structures interpretable in models of bounded arithmetic
Thapen, N
ANNALS OF PURE AND APPLIED LOGIC, 2005, 136 (03) : 247 - 266
[27] APPROXIMATE COUNTING BY HASHING IN BOUNDED ARITHMETIC
Jerabek, Emil
JOURNAL OF SYMBOLIC LOGIC, 2009, 74 (03) : 829 - 860
[28] Sprague–Grundy theory in bounded arithmetic
Satoru Kuroda
Archive for Mathematical Logic, 2022, 61 : 233 - 262
[29] Partially definable forcing and bounded arithmetic
Atserias, Albert
Mueller, Moritz
ARCHIVE FOR MATHEMATICAL LOGIC, 2015, 54 (1-2) : 1 - 33
[30] Bounded theories for polyspace computability
Bianconi, Ricardo
Ferreira, Gilda
Silva, Emmanuel
PORTUGALIAE MATHEMATICA, 2013, 70 (04) : 295 - 318

← 1 2 3 4 5 →