THE POLYNOMIAL-TIME HIERARCHY COLLAPSES IF THE BOOLEAN HIERARCHY COLLAPSES

被引：63

作者：

KADIN, J

机构：

[1] Cornell Univ, United States

来源：

关键词：

D O I：

10.1137/0217080

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：1263 / 1282

页数：20

共 27 条

[1]

AMIR A, 1987, 2ND P ANN STRUCT COM, P22

[2]

BEIGEL R, 1987, TR8707 J HOPK U DEP

[3]

Berman L., 1977, SIAM Journal on Computing, V6, P305, DOI 10.1137/0206023

[4]

CAI J, 1988, SIAM J COMPUT, V17

[5]

CAI J, 1986, SIAM J COMPUT, V16, P259

[6] PARITY, CIRCUITS, AND THE POLYNOMIAL-TIME HIERARCHY [J].

FURST, M ;

SAXE, JB ;

SIPSER, M .

MATHEMATICAL SYSTEMS THEORY, 1984, 17 (01) :13-27

[7]

HEMACHANDRA A, 1987, 199TH P ACM S THEOR, P110

[8]

Hopcroft J.E., 1979, INTRO AUTOMATA THEOR

[9]

IMMERMAN N, 1988, 3RD P STRUCT COMPL T, P112

[10]

KADIN J, IN PRESS J COMPUT SY