ENUMERATIVE COUNTING IS HARD

被引：34

作者：

CAI, JY

HEMACHANDRA, LA

机构：

[1] UNIV ROCHESTER,DEPT COMP SCI,ROCHESTER,NY 14627

[2] COLUMBIA UNIV,NEW YORK,NY 10027

[3] CORNELL UNIV,ITHACA,NY 14853

来源：

INFORMATION AND COMPUTATION | 1989年 / 82卷 / 01期

关键词：

D O I：

10.1016/0890-5401(89)90063-1

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：34 / 44

页数：11

共 28 条

[1]

ALLENDER EW, 1986, LECT NOTES COMPUT SC, V223, P1

[2] POLYNOMIAL TERSE SETS [J].

AMIR, A ;

GASARCH, WI .

INFORMATION AND COMPUTATION, 1988, 77 (01) :37-56

[3] ON COUNTING PROBLEMS AND THE POLYNOMIAL-TIME HIERARCHY [J].

ANGLUIN, D .

THEORETICAL COMPUTER SCIENCE, 1980, 12 (02) :161-173

[4]

[Anonymous], 1971, STOC 71, DOI DOI 10.1145/800157.805047

[5] RANDOM ORACLES SEPARATE PSPACE FROM THE POLYNOMIAL-TIME HIERARCHY [J].

BABAI, L .

INFORMATION PROCESSING LETTERS, 1987, 26 (01) :51-53

[6]

BEIGEL R, 1987, TR1806 U MAR DEP COM

[7]

CAI J, 1986, 18TH ACM S THEOR COM, P21

[8]

CAI J, 1989, IN PRESS P STACS 89

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

FURST, M ;

SAXE, JB ;

SIPSER, M .

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

[10]

GAREY N, 1979, COMPUTERS INTRACTABI

← 1 2 3 →