О линейной классификации четных и нечетных перестановочных матриц и сложности вычисления перманента

Изучена задача линейной классификации четности перестановочных матриц. Эта задача связана с анализом сложности класса алгоритмов вычисления перманента матрицы, обобщающего алгоритм знаков Кастелейна. Получены экспоненциальные нижние оценки для величины коэффициентов функционала, классифицирующего четные и нечетные перестановочные матрицы, в случае поля действительных чисел, и аналогичные линейные нижние оценки на ранг классифицирующего отображения в случае поля характеристики 2. Библ. 10. Фиг. 2.