Batas bawah pada kompleksitas Gaussian

Tentukan kompleksitas Gaussian dari matriks menjadi jumlah minimum operasi baris dan kolom elementer yang diperlukan untuk membawa matriks ke dalam bentuk segitiga atas. Ini adalah jumlah antara dan (melalui eleminasi Gaussian). Gagasan ini masuk akal di bidang apa pun.$n \times n$$0$$n^2$

Masalah ini tentu saja tampaknya sangat mendasar dan harus dipelajari. Yang mengejutkan, saya tidak tahu referensi apa pun. Jadi, saya akan senang dengan referensi yang ada. Tapi, tentu saja, pertanyaan utamanya adalah:

Apakah ada batas bawah eksplisit non-sepele yang diketahui?

Maksud saya non-trivier adalah superlinear. Hanya untuk menjadi jelas: Lebih dari bidang terbatas argumen penghitungan menunjukkan bahwa matriks acak memiliki urutan kompleksitas n ^ 2 (klaim serupa harus benar di atas bidang yang tak terbatas). Karenanya, apa yang kami cari adalah keluarga matriks eksplisit , misalnya, matriks Hadmard. Ini sama dengan kompleksitas sirkuit Boolean di mana kita tahu bahwa fungsi acak memiliki kompleksitas tinggi, tetapi kami sedang mencari fungsi eksplisit dengan properti ini.

Ini tampaknya merupakan masalah yang sangat sulit, terkait dengan yang lebih banyak dipelajari.

Misalkan kita menganggap matriks A yang dapat dibalik, dan mendefinisikan c (A) sebagai jumlah minimum operasi baris elementer yang diperlukan untuk mengurangi A ke matriks identitas. Ukuran kompleksitas ini lebih besar dari yang disarankan Moritz, jadi membuktikan batas superlinear hanya bisa lebih mudah.

Sekarang, operasi baris dapat dibalik . Oleh karena itu c (A) dapat secara ekuivalen didefinisikan sebagai jumlah minimum operasi baris yang diperlukan untuk menghasilkan A, mulai dari matriks identitas.

Perhatikan bahwa memproduksi A dengan cara seperti itu memunculkan sirkuit aritmatika untuk menghitung pengambilan peta x ke Ax. Fanin setiap gerbang adalah 2, dan jumlah gerbang non-input sesuai dengan jumlah operasi baris.

Tidak ada pengurangan yang jelas dalam arah sebaliknya (dari sirkuit ke urutan baris-op). Namun, kita dapat mengkarakterisasi c (A) dalam hal kompleksitas rangkaian aritmatika dari Ax dalam model rangkaian terbatas: Saya mengklaim bahwa c (A) sama dengan setengah dari jumlah minimum tepi dalam rangkaian aritmatika untuk A, dari fanin paling banyak 2 dan lebar n, di mana kami tidak mengenakan biaya untuk tepi yang mengarah ke gerbang fanin 1. (Saya menggunakan gagasan umum tentang lebar rangkaian di sini.) Ini dapat ditunjukkan dengan menggunakan ide sederhana yang digambarkan sebelumnya.

Sekarang inilah hubungannya dengan masalah yang dipelajari dengan baik: sudah menjadi masalah terbuka yang terkenal selama lebih dari 30 tahun untuk menunjukkan peta linear eksplisit Ax (atas bidang terbatas apa pun) yang membutuhkan jumlah gerbang superlinear dalam sirkuit fanin-2. Referensi klasik adalah Valiant, "Argumen grafik-teoretis dalam kompleksitas tingkat rendah", dan survei FTTCS baru-baru ini oleh Lokam juga membantu.

Dalam mempelajari c (A), kami menerapkan batasan lebar tambahan, tetapi karena batasan kami sangat lemah (lebar n) saya tidak mengantisipasi masalah menjadi lebih mudah. Tapi hei - saya ingin dibuktikan salah.

Ada referensi, dan itu sudah cukup tua. Saya menemukan mereka saat bekerja pada algoritma kombinatorial untuk perkalian matriks Boolean.

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

JW Moon dan L. Moser. Masalah Pengurangan Matriks. Matematika Komputasi 20 (94): 328–303, 1966.

Artikel harus dapat diakses di JSTOR.

Saya cukup yakin bahwa batas bawah hanyalah argumen penghitungan, dan tidak ada matriks eksplisit yang mencapai batas bawah yang diberikan.