Article collection "Mathematical Problems of Cybernetics" №16, Moscow, 2007
Bounds on complexity and algorithms for construction of deterministic conditional tests
The paper generalized the notion of a testing table for modelling decision trees of problems that may have several solutions, but only one needs to be found. Such problems include, for instance, many discrete optimization problems. We study upper bounds of time complexity and algorithms for constructing deterministic conditional tests of testing tables.