Consider a logic circuit with two-bit gates only. The length of each gate is the number of bit lines that the gate crosses. How hard is to compute the maximum length for a given circuit? Notice that two circuits are, say, isomorphic, if they differ only up to a permutation of the bit lines. Notice that there are clearly $n!$ ways to arrange $n$ bit lines.
$\begingroup$
$\endgroup$
11
-
1$\begingroup$ You need to provide more context. Is this supposed to resemble one side of a printed circuit board? Most circuit layouts use more than one layer. $\endgroup$– The Masked AvengerCommented Feb 4, 2014 at 19:01
-
2$\begingroup$ Are the gates rectangles arrayed in the plane? If so, perhaps your problem is reducible to computing the crossing number of a graph, which (as you likely know) is NP-hard, even for cubic graphs. $\endgroup$– Joseph O'RourkeCommented Feb 4, 2014 at 20:45
-
$\begingroup$ Indeed the circuit is a graph drawn on the plane with horizontal and vertical edges: the horizontal edges are segments of the bit lines; the vertical edges are the gates. To minimize the length we can only permute the bit lines. Surely the parameter of the question is the crossing number of this graph. However, I am not sure whether it is easy to compute it given the special structure. $\endgroup$– user3409Commented Feb 5, 2014 at 12:32
-
$\begingroup$ Thanks for the picture. I had a completely different idea of gate. I think of sorting networks when I see your picture. Perhaps that literature might have an answer for you. My guess is that it is as hard as graph isomorphism. $\endgroup$– The Masked AvengerCommented Feb 5, 2014 at 17:13
-
$\begingroup$ Try this idea: see if you can reduce Independent Set to this problem. $\endgroup$– The Masked AvengerCommented Feb 5, 2014 at 17:16
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
1
If I understand your question correctly, you're trying to find a permutation of the bit lines so the maximum gate "length" is as small as possible. This is called the bandwidth problem:
Given a graph $G = (V,E)$ find a permutation $\pi : V \rightarrow [1 \ldots n]$ such that $$\max_{(i,j) \in E} |\pi(i) - \pi(j)|$$ is minimized.
The wikipedia article has more information on the complexity (it's NP-hard and APX-hard) and algorithms. The bandwidth problem is interesting also because it was used to introduce the idea of volume-respecting embeddings.
answered Feb 12, 2014 at 1:00
-
$\begingroup$ Then this is the answer! Thank you! $\endgroup$– user3409Commented Feb 12, 2014 at 1:29