THE BOOLEAN HIERARCHY .1. STRUCTURAL-PROPERTIES

被引：110
作者：
CAI, JY
GUNDERMANN, T
HARTMANIS, J
HEMACHANDRA, LA
SEWELSON, V
WAGNER, K
WECHSUNG, G
机构：
[1] CORNELL UNIV,DEPT COMP SCI,ITHACA,NY 14853
[2] FRIEDRICH SCHILLER UNIV,MATH SECT,DDR-6900 JENA,GER DEM REP
[3] DARTMOUTH COLL,DEPT MATH & COMP SCI,HANOVER,NH 03755
[4] UNIV AUGSBURG,INST MATH,D-8900 AUGSBURG,FED REP GER
来源：
SIAM JOURNAL ON COMPUTING | 1988年 / 17卷 / 06期
关键词：
D O I：
10.1137/0217078
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
引用
收藏
页码：1232 / 1252
页数：21
相关论文
共 34 条
[1]  
AMIR A, 1987, 2ND P ANN STRUCT COM, P22
[2]  
[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047
[3]   RELATIVE TO A RANDOM ORACLE-A, PA NOT-EQUAL NPA NOT-EQUAL CO-NPA WITH PROBABILITY-1 [J].
BENNETT, CH ;
GILL, J .
SIAM JOURNAL ON COMPUTING, 1981, 10 (01) :96-113
[4]   ON THE UNIQUE SATISFIABILITY PROBLEM [J].
BLASS, A ;
GUREVICH, Y .
INFORMATION AND CONTROL, 1982, 55 (1-3) :80-88
[5]  
CAI J, IN PRESS SIAM J COMP
[6]  
CAI J, 1985, TR85688 CORN U COMP
[7]  
CAI J, 1985, TR85724 CORN U COMP
[8]   GRAPH MINIMAL UNCOLORABILITY IS DP-COMPLETE [J].
CAI, JY ;
MEYER, GE .
SIAM JOURNAL ON COMPUTING, 1987, 16 (02) :259-277
[9]  
CAI JY, 1986, LECT NOTES COMPUT SC, V223, P105
[10]  
CAI JY, 1986, THESIS CORNELL U ITH
1234