Lie patterns in search procedures (Q1090470): Difference between revisions

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.