CIRCUIT DEFINITIONS OF NONDETERMINISTIC COMPLEXITY CLASSES

被引：34
作者：
VENKATESWARAN, H
机构：
[1] Georgia Inst of Technology, Atlanta, GA
来源：
SIAM JOURNAL ON COMPUTING | 1992年 / 21卷 / 04期
关键词：
BOOLEAN CIRCUITS; ARITHMETIC CIRCUITS; NP; P; SKEW CIRCUITS; SEMIUNBOUNDEDNESS;
D O I：
10.1137/0221040
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
This paper considers restrictions on Boolean circuits and uses them to obtain new uniform circuit characterizations of nondeterministic space and time classes. It also obtains characterizations of counting classes based on nondeterministic time bounded computations on the arithmetic circuit model. It is shown how the notion of semi-unboundedness unifies the definitions of many natural complexity classes.
引用
收藏
页码：655 / 670
页数：16
相关论文
共 19 条
[1]  
BERTONI A, 1985, ANN DISCRETE MATH, V25, P65
[2]   RELATING TIME AND SPACE TO SIZE AND DEPTH [J].
BORODIN, A .
SIAM JOURNAL ON COMPUTING, 1977, 6 (04) :733-744
[3]   2 APPLICATIONS OF INDUCTIVE COUNTING FOR COMPLEMENTATION PROBLEMS [J].
BORODIN, A ;
COOK, SA ;
DYMOND, PW ;
RUZZO, WL ;
TOMPA, M .
SIAM JOURNAL ON COMPUTING, 1989, 18 (03) :559-578
[4]  
Cook S.A., 1979, P STOC 1979, P338
[5]   A TAXONOMY OF PROBLEMS WITH FAST PARALLEL ALGORITHMS [J].
COOK, SA .
INFORMATION AND CONTROL, 1985, 64 (1-3) :2-22
[6]   COMPLEXITY THEORY OF PARALLEL TIME AND HARDWARE [J].
DYMOND, PW ;
COOK, SA .
INFORMATION AND COMPUTATION, 1989, 80 (03) :205-226
[7]  
Goldschlager L. M., 1977, SIGACT News, V9, P25, DOI 10.1145/1008354.1008356
[8]  
Ladner R. E., 1975, SIGACT News, V7, P18, DOI 10.1145/990518.990519
[9]   POLYNOMIAL SPACE COUNTING PROBLEMS [J].
LADNER, RE .
SIAM JOURNAL ON COMPUTING, 1989, 18 (06) :1087-1097
[10]   THE COMPLEXITY OF FACETS (AND SOME FACETS OF COMPLEXITY) [J].
PAPADIMITRIOU, CH ;
YANNAKAKIS, M .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1984, 28 (02) :244-259
12