Table of Contents
This part is about considerations how the effort of deterministic algorithms (for example depth-first searches) as well as probabilistic methods increases depending on the problem input size. It should be investigated how the XiStrat™ games fall into the several classes discussed below.
On the other hand one could focus on algorithms that perform well in practice rather than on those with the best theoretical complexity. But with advances in hardware, in the long run implementations with more favourable complexity also run faster in practical computation.
In general the difference between polynomial and exponential algorithms is most important. Up to now it's not known if NP != P or PSPACE = P (but PSPACE = NPSPACE).
As already mentioned, general graph layouting and coloring are both NP-complete. And also the existence of a Hamiltonian cycle in a graph belongs to this class.
There are complexity considerations for typical tasks in group theory (see Chapter 11, Group Theory) as well. Things like computing the center, composition factors, Sylow subgroups of permutation groups are polynomial time, whereas finding isomorphisms of permutation groups or finding generators of automorphism groups of a graph fall into the so-called graph-isomorphism class. There exists no known P algorithm for graph-isomorphism testing, although the problem has also not been shown to be NP-complete, so some people invented a complexity class called 'graph isomorphism-complete' which is thought to be entirely disjoint from both NP-complete and from P. However, a polynomial time algorithm is known for planar graphs, graphs with restricted genus, graphs with bounded (maximal) degree of the vertices (valence) by a constant, or graphs with bounded Eigenvalue multiplicity (see for example [MathWorld], [Luk82] (btw. using substantially computational group theory), [Ser97] and [Rem03]).
Computing Gröbner bases is EXPSPACE-complete (in general). So probably we won't have an easy going there, but in any case they will provide a nice way to organize results once they have been achieved (and in our geometrical setting certainly the complexity is not similar to the worst case estimation anyway).
Now dealing with the strategy games, extending the actually finite problems to so called n × n board games (increasing n could translate into stellation (finer grained meshgrids). A general journey through the references tells us that some variants of n-in-a-row like games might have a polynomial-time strategy solution this way or the other, Hi-Q (see [Ueha98]) and some Dots-and-Boxes problems (see [Ber00]) are NP-complete or NP-hard, Reversi and Hex are in PSPACE-complete, Go (with Kos) using Japanese rules as well as Checkers and Chess are in EXPTIME-complete.
Whilst we have just come to know that here all general hope could be lost, nevertheless there are well-defined strategies about how to win elementary endgames (KQ:K, KR:K, KQ:KR, KBB:K, KNB:K and so on). For example in case of king, bishop and knight against king, there are at least 2 different ways (W-system and some triangle thing, see [Che91]). These strategies provide polynomial-time algorithms.
First of all those (winning) ways should be described in a mathematical manner (group theory), perhaps in analogy to the chains of subgroups used for Rubik's cube recipes.
Well, dreaming is allowed :-)