Some complexity results about packet radio networks (Corresp.)

It is shown that the decision problem regarding the membership of a point in the capacity region of a packet radio network is nondeterministic polynomial time hard (NP hard). The capacity region is the set of all feasible origin-to-destination message rates where feasibility is defined as the existence of any set of rules for moving the data through the network so that the desired rates are satisfied.