Kelas kompleksitas dari Matriks Inversion

Apakah membalik matriks dalam kelas Complexity ?$\text{P}$

Dari runtime saya akan mengatakan ya tetapi matriks terbalik dapat berisi entri di mana ukurannya tidak dibatasi secara polinomi oleh input?$\mathcal{O}(n^3)$

Ya, itu bisa dilakukan dalam waktu polinomial, tetapi buktinya cukup halus. Ini bukan hanya waktu, karena eliminasi Gaussian melibatkan mengalikan dan menambahkan angka, dan waktu untuk melakukan masing-masing operasi aritmatika tergantung pada seberapa besar mereka. Untuk beberapa matriks, nilai-nilai perantara dapat menjadi sangat besar, sehingga eliminasi Gaussian tidak harus berjalan dalam waktu polinomial.$O(n^3)$

Untungnya, ada yang algoritma yang tidak berjalan dalam waktu polinomial. Mereka membutuhkan sedikit lebih banyak perhatian dalam desain algoritma dan analisis algoritma untuk membuktikan bahwa waktu yang berjalan adalah polinomial, tetapi itu bisa dilakukan. Sebagai contoh, waktu berjalan dari algoritma Bareiss adalah sesuatu seperti [sebenarnya itu lebih kompleks dari itu, tetapi menganggapnya sebagai penyederhanaan untuk saat ini].$O(n^5 (\log n)^2)$

Untuk lebih banyak detail, lihat entri blog Dick Lipton Lupa Hasil dan Apa kompleksitas waktu sebenarnya dari eliminasi Gaussian? dan ringkasan Wikipedia .

Akhirnya, kata hati-hati. Waktu berjalan yang tepat tergantung pada bidang apa yang sedang Anda kerjakan. Diskusi di atas berlaku jika Anda bekerja dengan angka rasional. Di sisi lain, jika, misalnya, Anda bekerja pada bidang hingga (bilangan bulat modulo 2), maka eliminasi Gaussian naif tidak berjalan dalam waktu . Jika Anda tidak mengerti apa artinya ini, Anda mungkin dapat mengabaikan paragraf terakhir ini.$GF(2)$$O(n^3)$

Ada rumus untuk entri matriks terbalik yang memberikan setiap entri sebagai rasio dari dua determinan, satu minor dari matriks asli, dan yang lainnya dari seluruh matriks asli. Ini akan membantu Anda mengikat ukuran entri dalam matriks terbalik, jika Anda berhati-hati, diberi pengertian yang masuk akal tentang "ukuran" (perhatikan bahwa bahkan jika Anda mulai dengan matriks bilangan bulat, kebalikannya bisa berisi entri rasional).

Yang mengatakan, seringkali invers matriks dipelajari dari sudut pandang teori kompleksitas aljabar, di mana Anda menghitung operasi dasar terlepas dari besarnya. Dalam model ini, seseorang dapat menunjukkan bahwa kompleksitas invers matriks setara dengan kompleksitas multiplikasi matriks, hingga istilah polylogaritmik; pengurangan ini mungkin juga dapat membantu Anda mengikat ukuran koefisien.

Mengingat algoritma yang efisien dalam model teori kompleksitas aljabar, orang bertanya-tanya apakah itu menyiratkan algoritma yang sama efisiennya dalam model yang biasa; mungkinkah bahwa meskipun entri akhir adalah ukuran polinomial, perhitungannya melibatkan yang lebih besar? Ini mungkin bukan masalahnya, dan bahkan jika itu benar, masalahnya mungkin dapat dihindari dengan menggunakan teorema sisa China.