## 2 Background on the Identification Problem
### Identification Problem  
In the Shannon communication problem [17], a sender encodes its message in a manner that the receiver can perform a reliable _reconstruction_. That is, the receiver is interested in knowing which message was sent from the transmitter. In contrast, the coding design for the identification setting [49] is intended to conduct a different goal, namely to find out if a _desired_ message was sent by the transmitter or not. Furthermore, we assume that prior to the communication, the transmitter is not informed of the message that the receiver seeks to identify. **Randomized identification:** The identification problem (which has been studied in various setting of deterministic or randomized protocols, in the context of communication complexity; see [53; 54]) in communication theory is initiated by [PERSON] and [PERSON] in [49], where a randomized encoder is employed to select the codewords. In this problem, the codewords are chosen based on their corresponding distribution, and the codebook size grows double-exponentially in the codeword length \(n\), i.e., \(\sim 2^{2^{nR}}\)[49], where \(R\) is the coding rate. This observation stands different from the TR problem, where the size growth for the codebook is only exponentially with the codeword length, i.e., \(\sim 2^{nR}\). The realization of explicitly constructed RI codes features high complexity, and is often challenging for the applications of MC in the context of IoBNT; cf. [48] for further details. However, in [55; 56], explicit construction of RI codes using algebraic codes (Reed-Solomon) has been considered. **Deterministic identification:** Although the remarkable properties of RI schemes for the codebook size may seem appealing for some applications, in several practical settings, using a huge amount of randomness may not be favorable. Examples include MC, where implementation in the nano-scaled environment is prohibitive [51], or in a pessimistic jamming scenario, where it is assumed that the radar jammer has access to the whole codebook [57]; therefore, using randomness results in extra expenses and does not guarantee a benefit. Additionally, deterministic codes typically offer advantages such as ease of implementation, simulation experimentation [29; 30], and systematic construction [31]. The motivation of [PERSON] and [PERSON] to develop the RI problem [49] is probably traced back to the work of [PERSON][33], who considered DI from a communication complexity perspective (an important observation regarding the behavior of the identification function has been well studied in communication complexity, where the out-performance of randomized protocols over the deterministic protocols (exponential gap between the two classes) for computing such a function is established; for instance, while the error-free deterministic complexity of the identification function is lower bounded by \(\log m\), where \(m\) is the length of message, for the randomized protocol and when \(\varepsilon\) error is allowed in computation of the identification function, only \(O(\log\log m+1/\varepsilon)\) bits suffices; see [54; 58] for further details); that is, where the codewords are determined by a deterministic function from the messages. Moreover, it seems that [PERSON] and [PERSON] were inspired to show that employing randomness similar to what has been accomplished in the communication complexity field yields an advantage of _exponential gap_ compared to the DI problem (a detailed comparison of codebook sizes in DI and RI problem over various channel models can be found in [48]) for the codebook size. In application cases where complexity is restricted, DI could be preferred over RI. For instance, in MC systems, where the development and deploying of a huge number of random sources (distributions) may not be clear.