Consequences
Given that GG is PSPACE-complete, no polynomial time algorithm exists for optimal play in GG unless P = PSPACE. However, it may not be as easy to prove the complexity of other games because certain games (such as chess) contain a finite number of game positions — making it hard (or impossible) to formulate a mapping to a PSPACE-complete problem. In spite of this, the complexity of certain games can still be analyzed by generalization (e.g., to an n × n board). See the references for a proof for generalized Go, as a corollary of the proof of the completeness of GG.
Read more about this topic: Generalized Geography
Famous quotes containing the word consequences:
“The consequences of our actions grab us by the scruff of our necks, quite indifferent to our claim that we have “gotten better” in the meantime.”
—Friedrich Nietzsche (1844–1900)
“Without being forgiven, released from the consequences of what we have done, our capacity to act would ... be confined to one single deed from which we could never recover; we would remain the victims of its consequences forever, not unlike the sorcerer’s apprentice who lacked the magic formula to break the spell.”
—Hannah Arendt (1906–1975)
“We are still barely conscious of how harmful it is to treat children in a degrading manner. Treating them with respect and recognizing the consequences of their being humiliated are by no means intellectual matters; otherwise, their importance would long since have been generally recognized.”
—Alice Miller (20th century)