On the Complezity of Three-Player Snort Played on Complete Graphs

摘要：

Snort is a map-coloring game invented by Simon Norton where to establish who has a winning strategy on a general graph is a PSPACE-complete problem. Three-player Snort is a three-player version of Snort where cooperation between players is a key-factor to determine the winning coalition. In this paper, we show that three-player Snort played on complete graphs, that is extremely easy to solve in normal play convention, becomes an NP-complete problem in mis`ere play convention.

作者: Alessandro Cincotti

作者单位: School of Information Science Japan Advanced Institute of Science and Technology 1-1 Asahidai, Nomi, Ishikawa 923-1292 Japan

会议类型: 国际会议

会议名称: 2009 2nd IEEE International Conference on Computer Science and Information Technology(第二届计算机科学与信息技术国际会议 ICCSIT2009)

会议地点: 北京

会议语种:英文

页码: 2016-2018

在线出版日期: 2009-08-08（万方平台首次上网日期，不代表论文的发表时间）