Нижние оценки временной сложности детерминированных условных тестов

Деревья решений используются в различных приложениях как алгоритмы решения задач и как способ представления информации. Один из основных подходов к исследованию деревьев решений состоит в применении методов математической теории тестов. При этом моделью задачи служит тестовая таблица, а моделью дерева решений — условный тест. В работе понятие тестовой таблицы обобщается с целью моделирования задач, у которых имеется несколько решений и требуется найти хотя бы одно из них. К числу таких задач относятся, например, многие задачи дискретной оптимизации. Для обобщенных тестовых таблиц получены нижние оценки временной сложности детерминированных условных тестов и рассмотрен подход к доказательству нижних оценок сложности.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 93–012–488.