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.

Decision trees, discrete optimization, testing tables, deterministic conditional tests

Mathematical problems and theory of numerical methods