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)
“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)
“The medium is the message. This is merely to say that the personal and social consequences of any medium—that is, of any extension of ourselves—result from the new scale that is introduced into our affairs by each extension of ourselves, or by any new technology.”
—Marshall McLuhan (1911–1980)