8
$\begingroup$

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.

$\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$ 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$ 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$
    – user3409
    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$ Feb 5, 2014 at 17:13
  • $\begingroup$ Try this idea: see if you can reduce Independent Set to this problem. $\endgroup$ Feb 5, 2014 at 17:16

1 Answer 1

10
+100
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Then this is the answer! Thank you! $\endgroup$
    – user3409
    Feb 12, 2014 at 1:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.