On identifying codes in binary Hamming spaces (Q696908)

This paper studies the asymptotic minimum sizes \(M_r(n)\) of binary \(r\)-identifying codes \(C\subset \{ 0,1\}^n\). That means that all the sets \(B_r(x)\cap C\) are nonempty and distinct. The result is \[ \lim_{n\to \infty} n^{-1}M_{\lfloor \rho n \rfloor} (n) =1+\rho \log_2 \rho +(1-\rho) \log_2 (1-\rho). \] For linear codes, it is shown that the problem of determining whether a given code is \(r\)-identifying is \(\Pi_2\)-complete by reducing a \(\forall \exists \) 3-dimensional matching problem to it.