In this paper we discuss the complexity of a dynamic spectrum management problem within a multi-user communication system with K users and N available tones. In this problem a common utility function is optimized. In particular, so called min-rate, harmonic mean and geometric mean utility functions are considered. The complexity of the optimization problems with these utility functions is already discussed in  for different cases. However, the complexity for the case N = 2, K arbitrary is an open question. In this paper we show that these cases are also NP- hard by a reduction from the partitioning problem for the min-rate utility function, and from the independent set problem for the harmonic mean and geometric mean utility functions.
View On an open question about the complexity of a dynamic spectrum management problem