COMPLEXITY OF PROBLEMS IN GAMES, GRAPHS AND ALGEBRAIC EQUATIONS

被引：39

作者：

FRAENKEL, AS ^{[1
]}

YESHA, Y ^{[1
]}

机构：

[1] WEIZMANN INST SCI,DEPT APPL MATH,REHOVOT 76100,ISRAEL

来源：

DISCRETE APPLIED MATHEMATICS | 1979年 / 1卷 / 1-2期

关键词：

D O I：

10.1016/0166-218X(79)90012-X

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We prove NP-hardness of six families of naturally defined, interesting board games. Some of them are only just hard" in the sense that slight variations of them are polynomial. We further prove NP-completeness of two problems on digraphs which are related to game strategies; and NP-completeness and NP-hardness respectively of two classical problems of abstract algebra concerning the existence of solutions of algebraic equations. Also these problems were suggested by an investigation in combinatorial game theory. © 1979."

引用

页码：15 / 30

页数：16

共 18 条

[1]

Aho A. V., 1974, DESIGN ANAL COMPUTER

[2]

Banerji R. B., 1971, P S COMP AUT, P337

[3]

Berge C., 1962, THEORY GRAPHS ITS AP

[4]

Chvatal V., 1973, CRM300 U MONTR CTR R

[5]

Conway J.H., 1976, NUMBERS GAMES

[6]

EVEN S, 1975, 7TH P ANN ACM S THEO, P66

[7]

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

[8] THEORY OF ANNIHILATION GAMES [J].

FRAENKEL, AS ;

YESHA, Y .

BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 1976, 82 (05) :775-777

[9]

FRAENKEL AS, 1977, NOTICES AM SOC, V24, pA33

[10]

FRAENKEL AS, 1978, JUN P S COMB MATH OP

← 1 2 →