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 horror of Gandhi’s murder lies not in the political motives behind it or in its consequences for Indian policy or for the future of non-violence; the horror lies simply in the fact that any man could look into the face of this extraordinary person and deliberately pull a trigger.”
—Mary McCarthy (1912–1989)
“There is not much that even the most socially responsible scientists can do as individuals, or even as a group, about the social consequences of their activities.”
—Eric J. Hobsbawm (b. 1917)
“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)