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 :
بازگشت