## 4 DKI Capacity Region of the BSC
### Main Results
\begin{array}{ll}\left\{\left(R,\kappa\right);\,0\leq R\leq H(A),\,\kappa=0 \right\}&\text{if }A<1/2,\\ \left\{\left(R,\kappa\right);\,0\leq R\leq 1,\,\kappa=0\right\}&\text{if }A\geq 1/2, \end{array} \right. \tag{25}\]  
which is the closure of the inner bound. Therefore, since the closure of the inner bound region calculated in (24) coincides with the outer bound region given in (25), we obtain a closed form formula for the DI capacity of the BSC as follows:  
\[\mathbb{C}_{\text{DI}}(\mathcal{B},M)=\mathbb{C}_{\text{DKI}}(\mathcal{B},M,K= 1)=\left\{ \begin{array}{ll}H(A)&\text{if }A<1/2,\\ 1&\text{if }A\geq 1/2,\end{array} \right. \tag{26}\]  
where there is a Hamming constraint, and  
\[\mathbb{C}_{\text{DI}}(\mathcal{B},M)=1, \tag{27}\]  
where there is no Hamming constraint. This concludes the proof of Corollary 1. Proof. : The proof of Theorem 1 comprises two components, presented in Sections 4.2 and 4.3, respectively, which are the achievability and converse proofs. Here, we summarize some key findings from the proof of Theorem 1. \(\diamondsuit\)Input constraint: Theorem 1 reveals an important observation regarding the impact of the input constraint (when it is effective, i.e., \(0<A<1/2\)) on the inner and outer regions formulas for the DKI capacity. In contrast to previous results for DI over Gaussian channel [32] or DKI over slow fading channel [51], where the capacity bounds does not reflect the impact of the input constraint, our results for DKI over the BSC in this paper reflect the impact of the Hamming weight constraint on the inner and outer regions. \(\diamondsuit\)Scale of codebook: The inner and outer bounds on the DKI capacity region given in Theorem 1 are valid in the standard scale for the codebook size, i.e., \(M=2^{nR}\), where \(R\) is the coding rate. This result coincides the conventional behavior of the codebook size for TR [17] and DI [32] problems over the BSC. Other scales higher than the exponential for the codebook size of K-identification problem are reported in the literature; see Figure 4.  
\(\diamondsuit\)Scale of goal message set: Theorem 1 unveils that the size of the set of the goal messages scales exponentially in the codeword length, i.e., \(\sim\!\!2^{n\kappa}\). In particular, the result in Theorem 1 about size of the goal message set constitutes of the subsequent three cases in terms of \(K\):  
* DI, \(K=1\): In this scenario, the goal message set is a degenerate case; that is, \(K=\left\{i\right\}\), with \(i\in\llbracket M\rrbracket\), and is equivalent to the standard identification setup (\(\kappa=0\)), where \(|K|=K=1\). As a result, the identification setup in randomized regimes [49] and deter ministic regimes [32] can be thought of as a particular instance of the K-identification that is examined in this work. See Corollary 1 for further details. Constant \(K>1\)The scenario where \(\kappa\to 0\) as \(n\to\infty\) is implied by a constant \(K>1\). Our capacity bounds in Theorem 1 on the attainable rate pairs \((R,\kappa)\) are the same as those for \(K=1\). That is, the result in this cases converge to those for \(K=1\) given in Corollary 1, for the asymptotic \(n\to\infty\). Growing KThe fact that a trustworthy K-identification is still attainable, even in cases where \(K\) scales with the codeword length as \(\sim\)\(2^{n\kappa}\) for some \(\kappa\in[0,1)\), is another significant finding of Theorem 1 ; see Figure 5.  
We provide the inner bound proof in Section 4.2 and the outer bound proof in Section 4.3 as the proof of Theorem 1.