Bases for AC0 and Other Complexity Classes

被引：1

作者：

Mazzanti, Stefano ^{[1
]}

机构：

[1] Univ Iuav Venezia, Dipartimento Culture Progetto, I-30123 Venice, Italy

来源：

FUNDAMENTA INFORMATICAE | 2015年 / 136卷 / 04期

关键词：

concatenation recursion on notation; substitution basis;

D O I：

10.3233/FI-2015-1165

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Function complexity classes are defined as the substitution closure of finite function sets by improving a method of elimination of concatenation recursion from function algebras. Consequently, the set of AC(0) functions and other canonical complexity classes are defined as the substitution closure of a finite function set.

引用

页码：433 / 460

页数：28

共 17 条

[1]

Allender E., 2009, CHAPMAN HALL CRC APP, V1

[2] ON UNIFORMITY WITHIN NC1 [J].

BARRINGTON, DAM ;

IMMERMAN, N ;

STRAUBING, H .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1990, 41 (03) :274-306

[3]

Clote P, 1999, STUD LOGIC, V140, P589

[4]

Clote P., 1995, FEASIBLE MATH

[5]

CLOTE P, 1990, FEASIBLE MATH

[6]

Cook S., 2010, LOGICAL FDN PROFF CO

[7] Uniform constant-depth threshold circuits for division and iterated multiplication [J].

Hesse, W ;

Allender, E ;

Barrington, DAM .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2002, 65 (04) :695-716

[8] Function algebraic characterizations of the polytime functions [J].

Ishihara, H .

COMPUTATIONAL COMPLEXITY, 1999, 8 (04) :346-356

[9]

Jones J. P., 1988, P 1 C CAN NUMB THEOR, P255

[10]

Marcenkov S. S., 1969, MATH NOTES, V5, P336

← 1 2 →