Anulowanie i wyznacznik

9

Algorytm Berkowitza zapewnia obwód wielomianowy o głębokości logarytmicznej do wyznaczania macierzy kwadratowej z wykorzystaniem mocy macierzy. Algorytm domyślnie wykorzystuje anulowanie. Czy anulowanie jest niezbędne do uzyskania obwodu wielomianowego o głębokości logarytmicznej lub liniowej w celu obliczenia wyznacznika (i każdego możliwego najlepszego obwodu na stałe)? Czy istnieją dolne granice w pełni wykładnicze (nie tylko superpolinomalne lub sub wykładnicze) dla tych problemów z wykorzystaniem obwodów bez anulowania?

— T ....
źródło

2

w pewnym sensie intuicyjnym, bez odwołań, wyznacznikiem jest to samo, co na stałe

— Sasho Nikolov

11

Tak, anulowania są potrzebne, a dolne granice dotyczą modeli monotonicznych i modeli nieprzemiennych, w których anulowanie jest niemożliwe. Zobacz dyskusję w obwodach arytmetycznych Monotone . Badanie złożoności obwodu arytmetycznego można znaleźć w http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf

— Noam
źródło

1

Ktoś JIC ma problem, że obwody monotoniczne (stałe bez -ve) nie mogą obliczyć wyznacznika w sposób trywialny (ponieważ zawiera on -ve cefs). Zdefiniuj formalne monomialy indukcyjnie w następujący sposób: Jeśli

f = g_{1} + g_{2}

$f = g_1 + g_2$ , a następnie formalne monomiały z

f

$f$ jest unia związku

g_{1}

$g_1$ i

g_{2}

$g_2$ . Gdyby

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

$f = g_1 \times g_2$ , wówczas wszystkie formalne monomale są monomialami uzyskanymi przez wzięcie jednego z nich

g_{1}

$g_1$ i pomnożenie przez jeden z

g_{2}

$g_2$ . Dolna granica Jerrum-Snira działa tak długo, jak długo obwód spełnia właściwość, że formalne jednomianowe pierwiastki są równe niezerowym jednomianom obliczonego wielomianu.

— Ramprasad

1

Myślę, że ten artykuł bezpośrednio odpowiada na twoje pytanie.

Anulowanie ma potęgę wykładniczą w obliczaniu wyznacznika

Sengupta pokazuje, że nawet jeśli użyjesz odejmowania (stąd obwód nie jest monotoniczny), ale o ile nigdy nie „anulujesz” żadnych obliczonych monomianów, to determinantą obwodu macierzy wielkości jest obliczanie obwodu $n \times n$ ma przynajmniej rozmiar $n(2^{n-1}-1)$ .

— Thatchaphol
źródło