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.