A Combinatorial Problem Which Is Complet
โ
Even, S.; Tarjan, R. E.
๐
Article
๐
1976
๐
Association for Computing Machinery
๐
English
โ 537 KB
This paper considers a generalization, called the Shannon switching game on vertices, of a familiar board game called Hex. It is shown that determining who wins such a game if each player plays perfectly is very hard; in fact, if this game problem is solvable in polynomial time, then any problem sol