Implikasi mendekati penentu

Dengan risiko tidak memahami rincian pertanyaan dengan benar: Mampu memperkirakan determinan dalam faktor apa pun mengharuskan Anda untuk memutuskan apakah matriks persegi tunggal atau tidak, yang seharusnya memiliki beberapa konsekuensi.

Untuk satu hal, ini memberikan tes acak apakah grafik umum memiliki pencocokan sempurna (melalui matriks Tutte dan Schwarz-Zippel). Saya tidak berpikir yang terakhir dikenal dalam logspace acak (misalnya, Kompleksitas Zoo mencantumkan pencocokan bipartit yang sempurna sama sulitnya dengan NL).

Magnus Wahlström
sumber

Terima kasih Magnus, meskipun saya benar-benar memikirkan kesalahan perkiraan aditif, dalam hal ini Anda tidak akan diminta untuk membedakan apakah sebuah matriks tunggal atau tidak. Perkiraan multilipatif juga mungkin menarik, jadi saat ini, saya tidak yakin apa definisi terbaik.

Lior Eldar

@LiorEldar, pasti bahkan dengan kesalahan perkiraan aditif, jika entri dalam matriks adalah bilangan bulat dan batas kesalahan aditif kurang dari 0,5 Anda memiliki tes singularitas yang sangat mudah?

Peter Taylor

Hai Peter Taylor, saya kira untuk mengatakan, katakanlah 0,5 ketepatan yang pertama-tama Anda perlukan untuk menentukan norma operator terbesar yang Anda dukung. Jadi misalnya jika input memiliki , maka kesalahan aditif penentu Anda dapat . Jadi, bahkan jika input Anda diberikan kepada Anda sebagai bilangan bulat terpotong, masing-masing dari bit, maka norma maksimal yang Anda diminta untuk mendekati penentu akan dalam hal bilangan bulat, yang berarti bahwa kesalahan aproksimasi adalah jauh lebih kecil dari relatif ke.

A

$A$

‖ A ‖ \leq 1

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

1 / p o l y (n)

$1/poly(n)$

l o g (n)

$log(n)$

n^{n}

$n^n$

0.5

$0.5$

1 / p o l y (n)

$1/poly(n)$

‖ A ‖

$\left\|A\right\|$

Lior Eldar

Saya pikir masalah dengan kesalahan aditif relatif terhadap norma adalah bahwa itu tidak benar-benar baik skala. Katakanlah saya memiliki algoritma yang memberikan kesalahan perkiraan relatif ke. Sekarang misalkan menjadi blok diagonal dibentuk menggunakan salinan sebagai blok. Kemudian, tetapi , jadi a kesalahan aditif untuk menskala ke aditif kesalahan untuk .

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'||$

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

Implikasi mendekati penentu

Jawaban: