Konsekwencje przybliżenia wyznacznika

$n\times n$ $\log^2(n)$ $1$ $\left\|A\right\|\leq 1$ $1/\text{poly}$

W związku z tym, o jakie „poprawne” przybliżenie należy zapytać - multiplikatywne lub addytywne? (patrz jedna z odpowiedzi poniżej).

determinant cc.complexity-theory

— Lior Eldar
źródło

Czy powinny być na prawdziwej pamięci RAM?

$\:$

Nie jestem pewien, czy właściwie rozumiem pytanie, ale jeśli odwołujesz się do precyzji arytmetyki, to zakładam, że każda liczba rzeczywista jest przechowywana w log (n) bitach.

— Lior Eldar

Niebezpieczeństwo niewłaściwego zrozumienia szczegółów pytania: umiejętność przybliżenia wyznacznika w ramach dowolnego czynnika wymaga zdolności do decydowania, czy macierz kwadratowa jest pojedyncza, czy nie, co powinno mieć pewne konsekwencje.

Po pierwsze, daje losowy test sprawdzający, czy ogólny wykres ma idealne dopasowanie (za pomocą macierzy Tutte i Schwarz-Zippel). Nie sądzę, aby to drugie było znane w losowej przestrzeni logicznej (np. Zoo Złożoności wymienia dwustronne idealne dopasowanie jako trudne dla NL).

— Magnus Wahlström
źródło

Dzięki Magnus, chociaż tak naprawdę myślałem o addytywnym błędzie aproksymacji, w którym to przypadku nie będziesz musiał rozróżniać, czy macierz jest pojedyncza, czy nie. Interesujące może być również przybliżenie wielopłaszczyznowe, więc nie jestem pewien, jaka jest najlepsza definicja.

— Lior Eldar

@LiorEldar, z pewnością nawet z błędem aproksymacji addytywnej, jeśli wpisy w macierzy są liczbami całkowitymi, a granica błędu addytywnego jest mniejsza niż 0,5, masz niezawodny test osobliwości?

— Peter Taylor

Cześć Peter Taylor, myślę, że tak powiem, powiedz 0,5 precyzji, że najpierw musisz jakoś określić największą obsługiwaną normę operatora. Na przykład, jeśli twoje wejście

, to twój błąd addytywności może wynosić

A

$A$

‖ A ‖ \leq 1

$\left\|A\right\|\leq 1$

. Tak więc, nawet jeśli wejście jest podawany w postaci liczb całkowitych ściętego, każda o

bitów, a maksymalna norma dla których wymaga się w przybliżeniu wyznacznik byłoby

chodzi o całkowite, co oznacza, że

1 / p o l y (n)

$1/poly(n)$

l o g (n)

$log(n)$

n^{n}

$n^n$

0.5

$0.5$ błąd aproksymacji jest znacznie mniejszy niż

stosunku do

1 / p o l y (n)

$1/poly(n)$

‖ A ‖

$\left\|A\right\|$

— Lior Eldar

Myślę, że problem z addytywnym błędem w stosunku do normy polega na tym, że tak naprawdę nie ładnie się skaluje. Powiedzmy, że mam algorytm, który dał błąd aproksymacji

stosunku do

. Teraz niech

będzie

blokową macierzą ukośną utworzoną przy użyciu

kopii

jako bloków. To

1 / p o l y (n)

$1/poly(n)$

| | A | |

$||A||$

A^{'}

$A'$

n^{3} \times n^{3}

$n^3 \times n^3$

n^{2}

$n^2$

A

$A$

| | A | | = | | A^{'} | |

$||A||=||A'||$ , ale

, więc a

błąd addytywności dla

skalowany do błędu addytywności

dla

det (A^{'}) = det (A)^{n^{2}}

$\det(A')=\det(A)^{n^2}$

| | A^{'} | | / p o l y (n)

$||A'||/poly(n)$

d e t (A^{'})

$det(A')$

O (1)

$O(1)$

d e t (A)

$det (A)$

— Kevin Costello,