Эта задача связана с анализом сложности класса алгоритмов вычисления перманента матрицы, обобщающего алгоритм знаков Кастелейна. <...> Получены экспоненциальные нижние оценки для величины коэффициентов функционала, классифицирующего четные и нечетные перестановочные матрицы, в случае поля действительных чисел, и аналогичные линейные нижние оценки на ранг классифицирующего отображения в случае поля характеристики 2. <...> DOI: 10.7868/S004446691702003X Под линейной классификацией множеств и векторов некоторого векторного пространства понимается такое линейное отображение , которое переводит векторы из и в непересекающиеся множества: S 1. <...> ВВЕДЕНИЕ S1 S2 ϕ () ( )SS чающего множество , т.е. такого линейного отображения ϕ , что ∉ϕ − кация множеств и равносильна различению множестваS2 Наиболее известным примером задачи оценки сложности линейного различения является задача построения линейных корректирующих кодов. <...> Весьма общий случай задачи линейного различения известен как “критическая проблема” Крапо и Рота (подробнее см. <...> ). S1 d В настоящей работе мы рассматриваем линейную классификацию перестановочных матриц по четности. <...> Поскольку матричные элементы у перестановочных матриц принимают значения 0 или 1, их можно рассматривать над любым полем. <...> Сложность линейной классификации в данном случае определяется максимумом величины коэффициентов линейного функционала, различающего множества четных и нечетных перестановочных матриц. <...> R Интерес к задаче классификации перестановочных матриц по четности связан с одним подходом к вычислению перманента. <...> Напомним, что перманент матрицы определяется как X perXxπ() π∈ = =, S i 1 ∑∏ n ii n где – множество перестановок степени n. <...> Перманент является трудным многочленом как в модели алгебраических схем, так и в стандартной модели вычисления, в которой задача вычисSn 1)Работа выполнена при финансовой поддержке РФФИ (код проекта 14-01-00641) и программы гос. поддержки ведущих ун-тов РФ “5-100”. <...> Линейная <...>