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