OK. So crossing and turning wires we do not do directly.
For turning wires, we note that our procedure for duplicating wires can produce duplicates at different angles from the originals.
Crossing wires is hard. We do this on the predicate level. Essentially we are reducing to the problem PLANAR circuit SAT.
OK. So we have NOT gates. We can produce an AND gate (i.e. C = A AND B) using the following predicates:
A OR (NOT C)
B OR (NOT C)
C OR (NOT A) OR (NOT B)
(and noting that these can be arranged in a nice planar manner)
To simulate crossing wires is hard (note though that we only simulate crossing wires)
The idea is to produce a device with inputs A,B,C,D with A and B on the left and right, and C and D coming from up and down that is satisfiable if and only if A = B and C = D.
We will have four intermediate arbitrarily chosen values W,X,Y,Z that are arranged vertically between A and B.
We construct something that looks like the following:
.
..........C...............
..........|...............
...X AND (A OR (NOT B))...
|---------|--------------|
A.........X..............B
|---------|--------------|
|..X AND (A OR (NOT B))..|
|.........|..............|
A.........C..............B
.
We compute the X AND (A OR (NOT B)) as (X AND A) OR (X AND NOT B), so that it can be done in a planar manner. We additionally attach similar gadgets with the expressions
Y AND ((NOT A) OR B)
NOT [ Z AND (A OR (NOT B))]
NOT [ W AND ((NOT A) OR B)]
Note that all of these expressions are equal to both C and D, so C=D. Note that if A = B, the (A OR (NOT B))'s and ((NOT A) OR B)'s are always true, so W,X,Y,Z can be picked to make this work out. On the other hand, if A is not equal to B, then one of these expressions will fail. For example
C = X AND (A OR (NOT B))
is satisfyable unless A = 0, B = 1, C = 1. The other expressions rule out the other three combinations of (A,B,C) where A is not B.
Hence this gadget allows us to simulate wire crossing.
[Last edited by Daneel at 04-20-2007 03:52 AM]
