В этом отношении, какое «правильное» приближение нужно запрашивать - мультипликативное или аддитивное? (см. один из ответов ниже).
determinant
cc.complexity-theory
Лиор Эльдар
источник
источник
Ответы:
С риском неправильного понимания деталей вопроса: способность аппроксимировать детерминант в рамках любого фактора требует умения решать, является ли квадратная матрица единственной или нет, что должно иметь некоторые последствия.
Во-первых, он дает рандомизированный тест на то, имеет ли общий граф идеальное соответствие (через матрицу Тутте и Шварца-Циппеля). Я не думаю, что последнее известно в рандомизированном лог-пространстве (например, в Зоопарке Сложности перечисляются двудольные идеальные совпадения как сложные для NL).
источник