Lie patterns in search procedures
We investigate the problem of identifying an unknown set \(A\subset \{1,...,n\}\) using m queries of the form ''i\(\in A?''\) or, more generally, admitting all Boolean combinations of such queries. The answers need not always be true but their sequence has to follow one of the lie patterns from a prescribed set \({\mathcal H}\subset \{0,1\}^{\{1,...,m\}}\) (a 1 on the ith place forces the informing source to say the truth and a 0 to lie). We characterize those sets \({\mathcal H}\) for which the identification of A is possible and deal with the problem of the minimal size of \({\mathcal H}\) for which the set A can be hidden.
scientific article; zbMATH DE number 4007749