pratt@cs.stanford.edu (12/05/89)
(Is it ok if I send this stuff direct to you instead of posting it to
comp.parallel? Easier for me that way. -v)
====================================
From: James Price Salsman <js7a+@andrew.cmu.edu>
A four-by-four torus is isomorphic to a 2x2x2x2 hypercube.
On the other hand, a 2^8 hypercube is isomorphic to a
4x4x4x4 hypertoroid.
Two side remarks on this. The general case of course is that a 2^{2n}
hypercube is isomorphic to a 4^n hypertorus. The other thing is that
this observation is the underlying principle behind Karnaugh maps.
The isomorphism depends on the fact that in topology the circle *can*
be squared. That is, the square (meaning just its four edges, i.e. not
including the interior) is topologically equivalent to the circle
(meaning just its perimeter). Going around the square yields the Gray
code order 00-01-11-10-00, as found in Karnaugh maps. For some reason
digital design books don't point out this principle, which is a shame.
I used to point this out to the students in my machine organization
class at MIT in the 1970's, maybe the word has spread since.
Karnaugh maps are great for up to four Boolean variables because a 4x4
torus can be laid out in the plane. With six variables a 3D Karnaugh
map can be used (the plastic contraption that comes with the 3D
tic-tac-toe game should come in handy though I haven't tried it).
Beyond that it gets hard, but then the main application of Karnaugh
maps, finding a minterm representation of Boolean expressions, is after
all NP-complete. From a complexity viewpoint we should be grateful our
universe has only three spatial dimensions instead of say 1000 or
infinitely many. Navigation would be a famous open problem!
Vaughan Pratt
pratt@cs.stanford.edu