Последствия аппроксимации детерминанта

16

n×nlog2(n)1A11/poly

В этом отношении, какое «правильное» приближение нужно запрашивать - мультипликативное или аддитивное? (см. один из ответов ниже).

Лиор Эльдар
источник
1
Они должны быть в реальном ОЗУ?
Я не уверен, что правильно понял вопрос, но если вы ссылаетесь на точность арифметики, то я бы предположил, что каждое действительное число хранится в log (n) битах.
Лиор Эльдар

Ответы:

4

С риском неправильного понимания деталей вопроса: способность аппроксимировать детерминант в рамках любого фактора требует умения решать, является ли квадратная матрица единственной или нет, что должно иметь некоторые последствия.

Во-первых, он дает рандомизированный тест на то, имеет ли общий граф идеальное соответствие (через матрицу Тутте и Шварца-Циппеля). Я не думаю, что последнее известно в рандомизированном лог-пространстве (например, в Зоопарке Сложности перечисляются двудольные идеальные совпадения как сложные для NL).

Магнус Вальстрём
источник
Спасибо Магнус, хотя я на самом деле думал об аддитивной ошибке аппроксимации, и в этом случае вам не нужно будет отдельно указывать, является ли матрица единственной или нет. Мультипликативное приближение также может представлять интерес, поэтому сейчас я не уверен, какое определение лучше.
Лиор Эльдар
1
@LiorEldar, конечно, даже с аддитивной ошибкой аппроксимации, если записи в матрице являются целыми числами, а аддитивная граница ошибки меньше 0,5, у вас есть тест на исключительную надежность?
Питер Тейлор
Привет, Питер Тейлор, я думаю, что для того, чтобы сказать, скажем, точность 0,5, сначала нужно как-то указать самую большую норму оператора, которую вы поддерживаете. Так, например, если ваш вход имеет A 1 , то ваша аддитивная ошибка определителя может быть 1 / p o l y ( n ) . Таким образом, даже если ваш ввод дается вам в виде усеченных целых чисел, каждое из l o g ( nAA11/poly(n) битов, тогда максимальная норма, для которой вы должны приблизить определитель, будет n n в терминах целых чисел, что означает, что 0,5log(n)nn0.5ошибка аппроксимации намного меньше , чем по отношению к | | A1/poly(n) . A
Лиор Эльдар
Я думаю, что проблема с аддитивной ошибкой относительно нормы в том, что она не очень хорошо масштабируется. Скажем, у меня был алгоритм, который давал ошибку аппроксимации относительно | | A | | , Теперь пусть A будет n 3 × n 3 блок-диагональной матрицей, сформированной с использованием n 2 копий A в качестве блоков. Тогда | | A | | = , но det ( A )1/poly(n)||A||An3×n3n2A||A||=||A|| , поэтому a | | A | | / p o l y ( n ) аддитивная ошибка для d e t ( A ) масштабируется до O ( 1 ) аддитивной ошибки для d e t ( A ) . det(A)=det(A)n2||A||/poly(n)det(A)O(1)det(A)
Кевин Костелло