Some Completeness Results on Decision Trees and Group Testing

Abstract

The computational complexity of the group testing problem is investigated under the minimax measure and the decision tree model. We consider the generalizations of the group testing problem in which partial information about the decision tree of the problem is given. Using this approach, we demonstrate the NP-hardness of several decision problems related to various models of the group testing problem. For example, we show that, for several models of group testing, the problem of recognizing a set of queries that uniquely determines each object is co-NP-complete.