The relationship between the bandwidth of computational problems and their complexity
Moon-Jung Chung · 1981
The relationships between the time and space complexity of NP-Complete problems and their layout complexity are presented in this work. For the notions of layout complexity, cutwidth and bandwidth are considered. It is shown that many NP-Complete problems are log space hard for NTISP(poly,f(n)) when these problems are restricted to bandwidth f(n). Furthermore, several are complete for NTISP(poly, f(n)) when restricted to bandwidth f(n). Thus, with small bandwidth, many of them provide additional examples of NSPACE(log n) complete problems and are solvable in polynomial time. Bandwidth preserving reductions are studied, and it is shown that many reductions preserve bandwidth even when other restrictions such as node degree or planarity are imposed. It is also shown that cutwidth restrictions have similar properties as bandwidth restrictions The complexity relationships between cutwidth restricted problems and bandwidth restricted problems are studied. Several NP-Complete problems under cutwidth restriction f(n) are complete for NTISP(poly, f(n)). We show that many bandwidth preserving reductions also preserve cutwidth. It is known that, if P(NOT=)NP, then there are problems in NPI, where NPI is the set of problems in NP which are not in P and are not NP-Complete. This work suggests that bandwidth and cutwidth restricted versions of several NP-Complete problems are natural examples of problems in NPI.