The design of integrated circuits has achieved a
great deal of attention in the last decade.
In the routing phase, an
open layout problem has survived which is important from
both the theoretical and the practical point of view.
The channel routing problem has been known to be solvable in polynomial time
when there are only 2-terminal nets, and is proved
by Sarrafzadeh to be NP}-complete
in case that there exists nets containing at least six terminals. Also the
5-terminal case is claimed to be NP}-complete. In our paper, we give
a simple proof for the NP}-completeness of the 5-terminal channel
routing problem. This proof is based on a reduction from a special
version of the satisfiability problem. Based on the techniques introduced in
this paper and a result of HSS97} stating the NP}-completeness of
the 3-terminal switchbox routing problem, we prove the
4-terminal 3-sided switchbox routing problem to be NP}-complete.
