Pembatalan dan penentu

9

Algoritma Berkowitz menyediakan sirkuit ukuran polinomial dengan kedalaman logaritmik untuk penentu matriks kuadrat menggunakan kekuatan matriks. Algoritma secara implisit menggunakan pembatalan. Apakah pembatalan penting untuk mencapai sirkuit ukuran polinomial dengan kedalaman logaritmik atau linier untuk menghitung determinan (dan kemungkinan sirkuit terbaik untuk permanen)? Apakah ada batas penuh eksponensial (bukan hanya superpolinomial atau sub eksponensial) untuk masalah ini menggunakan sirkuit tanpa pembatalan?

circuit-complexity algebraic-complexity permanent arithmetic-circuits determinant T ....
sumber

2

dalam beberapa hal intuitif, tanpa pembatalan, determinan adalah hal yang sama dengan yang permanen

Sasho Nikolov

11

Ya, pembatalan diperlukan dan ada batas yang lebih rendah untuk monoton dan untuk model non-komutatif di mana pembatalan tidak mungkin. Lihat diskusi di sirkuit aritmatika Monoton . Survei kompleksitas sirkuit aritmatika dapat ditemukan di http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf

Noam
sumber

1

f = g_{1} + g_{2}

$f = g_1 + g_2$

f

$f$

g_{1}

$g_1$

g_{2}

$g_2$

f = g_{1} \times g_{2}

$f = g_1 \times g_2$

g_{1}

$g_1$

g_{2}

$g_2$ . Batas bawah Jerrum-Snir bekerja selama rangkaian memenuhi sifat bahwa monomial formal dari akar sama dengan monomial non-nol dari polinomial yang dihitung.

Ramprasad

1

Saya pikir makalah ini langsung menjawab pertanyaan Anda.

Pembatalan sangat kuat secara eksponensial untuk menghitung determinan

$n \times n$ $n(2^{n-1}-1)$

Thatchaphol
sumber

Pembatalan dan penentu

Jawaban: