О задаче выявления хунты для таблично заданных функций

$(n,k)$-хунта — это булева функция от $n$ переменных, которая зависит не более чем от $k$ этих переменных. Задача определения того, является ли данная булева функция $k$-хунтой, и нахождения этих $n-k$ несущественных переменных является широко распространенной в машинном обучении (сокращение несущественных признаков) и проектировании электронных схем (сокращение фиктивных переменных). Естественным обобщением данного понятия, широко встречающегося в данных и других областях, например в теории игр, является понятие переменной, оказывающей малое влияние на результаты вычисления функции. Отдельный интерес представляет вопрос: рассматриваются ли несущественные или маловлиятельные переменные по отдельности или ансамблем? Вычислительная эффективность решения данных задач чрезвычайно актуальна для приложений. В частности, это зависит от используемого представления булевой функции. В настоящей работе булевы функции задаются полными или частичными таблицами истинности (примерами наборов данных). Здесь представлены два полиномиальной временной сложности алгоритма для поиска хунт, а также обсуждается случай, когда можно, аппроксимируя заданную функцию, сделать маловлиятельные переменные несущественными.