О связи задач диагностического и проверяющего тестирования бесповторных функций

Рассматривается задача построения условного диагностического теста для бесповторных функций в произвольном базисе с помощью запросов значения функции в точке и запросов проверки произвольной подфункции на тождественное равенство постоянной. Устанавливается связь этой задачи с родственной задачей проверяющего тестирования, доказывается ее полиномиальная разрешимость для широкого класса булевых функций.
Работа выполнена при поддержке ФЦП “Научные и научно-педагогические кадры инновационной России” на 2009–2013 г.