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:
“Every expansion of government in business means that government in order to protect itself from the political consequences of its errors and wrongs is driven irresistibly without peace to greater and greater control of the nation’s press and platform. Free speech does not live many hours after free industry and free commerce die.”
—Herbert Hoover (1874–1964)
“Resistance is feasible even for those who are not heroes by nature, and it is an obligation, I believe, for those who fear the consequences and detest the reality of the attempt to impose American hegemony.”
—Noam Chomsky (b. 1928)
“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)