# A combinatorial problem concerned with logic circuits

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.

-
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. – The Masked Avenger Feb 4 '14 at 19:01
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. – Joseph O'Rourke Feb 4 '14 at 20:45
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. – Simone Severini Feb 5 '14 at 12:32
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. – The Masked Avenger Feb 5 '14 at 17:13
Try this idea: see if you can reduce Independent Set to this problem. – The Masked Avenger Feb 5 '14 at 17:16

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.