A UNIFORM CIRCUIT LOWER-BOUND FOR THE PERMANENT

被引：28

作者：

ALLENDER, E

GORE, V

机构：

[1] PRINCETON UNIV, PRINCETON, NJ 08544 USA

[2] UNIV CALIF LOS ANGELES, DEPT MATH, PROGRAM COMP, LOS ANGELES, CA 90024 USA

来源：

SIAM JOURNAL ON COMPUTING | 1994年 / 23卷 / 05期

关键词：

CIRCUIT COMPLEXITY; UNIFORMITY; PERMANENT; LOWER BOUNDS; COMPLEXITY CLASSES;

D O I：

10.1137/S0097539792233907

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The authors show that uniform families of ACC circuits of subexponential size cannot compute the permanent function. This also implies similar lower bounds for certain sets in PP. This is one of the very few examples of a lower bound in circuit complexity whose proof hinges on the uniformity condition; it is still unknown if there is any set in Ntime (2(no(1))) that does not have nonuniform ACC circuits.

引用

页码：1026 / 1049

页数：24

共 32 条

[1]

ALLENDER E, 1993, DIMACS SERIES DISCRE, V13, P21

[2]

ALLENDER E, IN PRESS INFORM COMP

[3]

ASPNES J, 1991, 23RD P ANN ACM S THE, P402

[4]

BARRINGTON D, 1992, 7TH P ANN IEEE STRUC, P86