COMPUTING A PERFECT STRATEGY FOR NXN CHESS REQUIRES TIME EXPONENTIAL IN N

被引：52

作者：

FRAENKEL, AS ^{[1
]}

LICHTENSTEIN, D ^{[1
]}

机构：

[1] UNIV CALIF BERKELEY,DEPT COMP SCI,BERKELEY,CA 94720

来源：

关键词：

D O I：

10.1016/0097-3165(81)90016-9

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

引用

页码：199 / 214

页数：16

共 11 条

[1]

FRAENKEL A, 1978, 19TH P ANN S F COMP, P55

[2]

Garey Michael R., 1979, COMPUTERS INTRACTABI

[3]

Lichtenstein D., 1978, 19th Annual Symposium on Foundations of Computer Science, P48, DOI 10.1109/SFCS.1978.17

[4] GO IS POLYNOMINAL-SPACE HARD [J].

LICHTENSTEIN, D ;

SIPSER, M .

[5]

MORRISON M, 1978, OFFICIAL RULES CHESS

[6] GOBANG IS P-SPACE-COMPLETE [J].

REISCH, S .

[7] HEX IS P-SPACE-COMPLETE [J].

REISCH, S .

[8]

ROBSON JM, 1980, TRCS8009 AUSTR NAT U

[9]

SAMELSON H, 1977, NOTICES AM MATH SOC, V24, P190

[10] PROVABLY DIFFICULT COMBINATORIAL GAMES [J].

STOCKMEYER, LJ ;

CHANDRA, AK .