Non-orthogonal multiple access (NOMA) is a promising radio access technology
for 5G. It allows several users to transmit on the same frequency and time
resource by performing power-domain multiplexing. At the receiver side,
successive interference cancellation (SIC) is applied to mitigate interference
among the multiplexed signals. In this way, NOMA can outperform orthogonal
multiple access schemes used in conventional cellular networks in terms of
spectral efficiency and allows more simultaneous users. This paper investigates
the computational complexity of joint subcarrier and power allocation problems
in multi-carrier NOMA systems. We prove that these problems are strongly
NP-hard for a large class of objective functions, namely the weighted
generalized means of the individual data rates. This class covers the popular
weighted sum-rate, proportional fairness, harmonic mean and max-min fairness
utilities. Our results show that the optimal power and subcarrier allocation
cannot be computed in polynomial time in the general case, unless P = NP.
Nevertheless, we present some tractable special cases and we show that they can
be solved efficiently.

本论文研究了多载波 NOMA 系统中，联合子载波和功率分配问题的计算复杂性，证明这些问题对于一大类目标函数即加权广义平均值是强 NP 难问题，然而，我们展示了一些易于处理的特殊情况，表明它们可以有效地求解。