DocumentCode
518286
Title
Three-player Toppling Dominoes is NP-complete
Author
Cincotti, Alessandro
Author_Institution
Sch. of Inf. Sci., Japan Adv. Inst. of Sci. & Technol., Nomi, Japan
Volume
1
fYear
2010
fDate
16-18 April 2010
Abstract
In two player games players are in conflict to each other and coalitions are not allowed but in three-player games two players can join their efforts against the third player. As a result, cooperation is a key-factor that deeply affects the complexity of three-player games. In Toppling Dominoes, cooperation can be much more difficult than competition and, as a consequence, three-player Toppling Dominoes played on a set of rows of dominoes is NP-complete.
Keywords
computational complexity; game theory; games of skill; NP-complete problem; three-player toppling dominoes; two player games; Computational complexity; Information science; Law; Legal factors; NP-complete problem; Tree graphs; combinatorial games; computational complexity;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Engineering and Technology (ICCET), 2010 2nd International Conference on
Conference_Location
Chengdu
Print_ISBN
978-1-4244-6347-3
Type
conf
DOI
10.1109/ICCET.2010.5485977
Filename
5485977
Link To Document