Complexity of problems in games, graphs and algebraic equations

AbstractWe prove NP-hardness of six families of naturally defined, interesting board games. Some of them are “only just hard” in the sense that slight variations of them are polynomial. We further prove NP-completeness of two problems on digraphs which are related to game strategies; and NP-completeness and NP-hardness respectively of two classical problems of abstract algebra concerning the existence of solutions of algebraic equations. Also these problems were suggested by an investigation in combinatorial game theory