Consider a logic circuit with twobit 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.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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 NPhard and APXhard) and algorithms. The bandwidth problem is interesting also because it was used to introduce the idea of volumerespecting embeddings. 

