Знаковая конвертация матриц

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