Resource Allocation for Secure Communication Systems: Algorithmic Solvability

Medium access control and in particular resource allocation is one of the most important tasks when designing wireless communication systems as it determines the overall performance of a system. For the particular allocation of the available resources it is of crucial importance to know whether or not a channel supports a certain quality-of-service (QoS) requirement. This paper develops a decision framework based on Turing machines and studies the algorithmic decidability of whether or not a QoS requirement is met. Turing machines have no limitations on computational complexity, computing capacity, and storage. They can simulate any given algorithm and therewith characterize the fundamental performance limits for today's digital computers. In this paper, secure communication and identification systems are considered both under channel uncertainty and adversarial attacks. While for perfect channel state information, the question is decidable since the corresponding capacity function is computable, it is shown that the corresponding questions become semidecidable in the case of channel uncertainty and adversarial attacks. This means there exist Turing machines that stop and output the correct answer if and only if a channel supports the given QoS requirement. Interestingly, the opposite question of whether a channel capacity is below a certain threshold is not semidecidable.