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
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;
Conference_Titel :
Computer Engineering and Technology (ICCET), 2010 2nd International Conference on
Conference_Location :
Chengdu
Print_ISBN :
978-1-4244-6347-3
DOI :
10.1109/ICCET.2010.5485977