Dolne granice złożoności Gaussa

Określić Gaussa złożoność danego matrycy, tak aby minimalna ilość elementarnych wierszy i kolumn operacji wymaganych do matrycy w postaci górnej trójkątnej. Jest to wielkość od do (poprzez eliminację Gaussa). Pojęcie ma sens w każdej dziedzinie.$n \times n$$0$$n^2$

Ten problem z pewnością wydaje się bardzo podstawowy i musiał zostać zbadany. O dziwo, nie znam żadnych referencji. Będę zadowolony z wszelkich odniesień. Ale oczywiście głównym pytaniem jest:

Czy znane są jakieś nietrywialne, wyraźne dolne granice?

Przez nietrywialne rozumiem superlinię. Żeby było jasne: ponad polami skończonymi argument zliczający pokazuje, że macierz losowa ma porządek złożoności n ^ 2 (podobne twierdzenie powinno być prawdziwe w przypadku pól nieskończonych). Dlatego szukamy wyraźnej rodziny macierzy, np. Macierzy Hadmarda. Jest to to samo, co w przypadku złożoności obwodu logicznego, w której wiemy, że funkcja losowa ma wysoką złożoność, ale szukamy funkcji jawnych z tą właściwością.

Wydaje się, że jest to bardzo trudny problem, związany z szerzej badanym.

Załóżmy, że bierzemy pod uwagę kwadratową odwracalną macierz A i definiujemy c (A) jako minimalną liczbę elementarnych operacji na wierszach potrzebnych do zredukowania A do macierzy tożsamości. Ta miara złożoności jest większa niż sugeruje Moritz, więc udowodnienie granic ponadliniowych może być łatwiejsze.

Teraz operacje na wierszach są odwracalne . Wynika z tego, że c (A) można równo zdefiniować jako minimalną liczbę operacji wiersza potrzebnych do wytworzenia A, zaczynając od macierzy tożsamości.

Zauważ, że wytworzenie A w taki sposób powoduje powstanie obwodu arytmetycznego do obliczenia mapy przyjmującej x do Ax. Fanin każdej bramki wynosi 2, a liczba bramek niepochodzących z wejścia odpowiada liczbie operacji rzędowych.

Nie ma żadnej oczywistej redukcji w odwrotnym kierunku (od obwodów do sekwencji rzędów). Nadal możemy scharakteryzować c (A) pod względem złożoności obwodu arytmetycznego Ax w modelu z ograniczonym obwodem: twierdzę, że c (A) jest równe połowie minimalnej liczby krawędzi w obwodzie arytmetycznym dla A, fanin co najwyżej 2 i szerokość n, gdzie nie pobieramy opłat za krawędzie prowadzące do bram fanin 1. (Używam tutaj zwykłego pojęcia szerokości obwodu). Można to pokazać za pomocą prostego pomysłu naszkicowanego wcześniej.

Oto związek z dobrze zbadanymi problemami: od ponad 30 lat znany jest otwarty problem z wyświetlaniem wyraźnej liniowej mapy Ax (na dowolnym skończonym polu), która wymaga superliniowej liczby bramek w obwodzie fanin-2. Klasycznym odniesieniem jest Valiant, „Teoretyczne wykresy w złożoności niskiego poziomu”, a pomocne są również niedawne ankiety FTTCS przeprowadzone przez Lokam.

Studiując c (A), nakładamy dodatkowe ograniczenie szerokości, ale ponieważ nasze ograniczenie jest tak słabe (szerokość n), nie przewiduję, że problem stanie się znacznie łatwiejszy. Ale hej - chciałbym, żeby mi się nie udało.

Istnieją referencje i są one dość stare. Natknąłem się na nich podczas pracy nad algorytmami kombinatorycznymi do mnożenia macierzy boolowskich.

$\Theta(n^2/log n)$$\log n$

JW Moon i L. Moser. Problem redukcji macierzy. Mathematics of Computation 20 (94): 328– 330, 1966.

Artykuł powinien być dostępny na JSTOR.

Jestem prawie pewien, że dolna granica jest tylko argumentem liczącym i nie podano żadnych wyraźnych macierzy osiągających dolną granicę.