Penentu dan Multiplikasi Matriks - Kesamaan dan perbedaan dalam kompleksitas algoritmik dan ukuran sirkuit aritmatika

Saya mencoba untuk memahami hubungan antara kompleksitas algoritmik dan kompleksitas rangkaian Determinants dan Matrix Multiplication.

Hal ini diketahui bahwa determinan dari suatu matriks dapat dihitung dalam waktu, di mana adalah waktu minimum yang diperlukan untuk memperbanyak dua matriks. Diketahui juga bahwa kompleksitas rangkaian penentu terbaik adalah polinomial pada kedalaman dan eksponensial. $n\times n$ $\tilde{O}(M(n))$ $M(n)$ $n\times n$ $O(\log^{2}(n))$ pada kedalaman 3. Tetapi kompleksitas sirkuit dari perkalian matriks, untuk setiap kedalaman konstan, hanya polinomial.

Mengapa ada perbedaan dalam kompleksitas rangkaian untuk determinan dan perkalian matriks, sementara diketahui bahwa dari perspektif algoritma, perhitungan determinan serupa dengan perkalian matriks? Secara khusus, mengapa kompleksitas sirkuit memiliki celah eksponensial pada kedalaman- ? $3$

Mungkin, penjelasannya sederhana tapi saya tidak melihatnya. Apakah ada penjelasan dengan 'ketelitian'?

Lihat juga: Formula terkecil yang diketahui untuk determinan

algebraic-complexity arithmetic-circuits matrix-product determinant T ....
sumber

Jawaban:

Pertimbangkan masalah nilai rangkaian dan evaluasi rumus Boolean untuk berbagai kelas kompleksitas kecil. Sejauh ini kompleksitas waktu sekuensial deterministik dari mereka adalah sama, tetapi mereka sangat berbeda dari perspektif kompleksitas sirkuit. Kesamaan dalam satu jenis sumber daya tertentu pada satu model tidak menyiratkan kesamaan untuk sumber daya lain dalam model lain. Satu masalah bisa sedemikian rupa sehingga kita dapat mengeksploitasi komputasi paralel untuk satu sementara kita tidak bisa melakukan itu untuk yang lain, namun kompleksitas waktu berurutannya bisa sama.

Kapan kita dapat mengharapkan hubungan yang lebih kuat antara kerumitan dua masalah lintas model dan sumber daya yang berbeda? Ketika keduanya adalah pengurangan yang kuat di antara mereka di kedua arah yang menghormati sumber daya dalam model tersebut.

$\mathsf{NL}$ $\mathsf{NC^2}$

Kaveh
sumber

O (n^{3})

$O(n^{3})$

n^{2}

$n^{2}$

T C^{0}

$\mathsf{TC^0}$

A C^{0}

$\mathsf{AC^0}$

Saya hanya melihat kompleksitas berurutan untuk saat ini.

T ....

Saya tidak yakin apakah saya mengikuti komentar Anda. Saya pikir posting saya menjawab pertanyaan dalam pengaturan Boolean (pertanyaannya tidak menyebutkan sirkuit aritmatika awalnya IIRC). Untuk pengaturan rangkaian aritmatika saya tidak tahu banyak, mudah-mudahan orang lain akan menjawab pertanyaan itu.

Kaveh

Saya akan mengatakan bahwa kesenjangan dalam pengaturan aritmatika memberitahu kita bahwa perkalian matriks secara inheren adalah tugas yang jauh lebih paralel daripada faktor penentu. Dengan kata lain, meskipun kompleksitas sekuensial dari kedua masalah tersebut saling berkaitan erat, kompleksitas paralelnya tidak begitu dekat satu sama lain.

$D(n)$ $n\times n$

O (\log n) \leq D (n) \leq O (\log^{2} n) .

$O(\log n)\le D(n) \le O(\log^2 n).$

3

$3$

(A \cdot B)_{i j} = \sum_{k} A_{i k} B_{k j}

$(A\cdot B)_{ij}=\sum_k A_{ik}B_{kj}$

Bruno
sumber

Saya tidak tahu apakah ini adalah jawaban untuk "mengapa kompleksitas sirkuit memiliki celah eksponensial pada kedalaman-3?", Tetapi setidaknya Anda memiliki bukti fakta ini adalah makalah Csanky.

Bruno

Jika saya mengerti dengan benar, Anda menyiratkan: untuk memiliki jumlah prosesor polinomial, seseorang perlu kedalaman logaritmik?

T ....

Saya tidak ingat model persis yang digunakan Csanky. Sebenarnya, ia sedang mempertimbangkan apa yang sekarang kita sebut sirkuit aritmatika dengan kipas-terikat . Jadi batas bawah cukup sepele dan perbandingan saya dengan perkalian matriks tidak relevan.

Bruno