Eliminasi Gaussian dalam hal Aksi Kelompok

Eliminasi gaussian menentukan determinan matrik polinomial-waktu. Pengurangan kompleksitas dalam menghitung determinan, yang merupakan penjumlahan dari istilah eksponensial, adalah karena adanya tanda-tanda negatif alternatif (kurangnya yang membuat komputasi permanen adalah mis. Lebih sulit daripada masalah N P - C ) . Ini mengarah pada semacam simetri dalam determinan, misalnya pertukaran sepasang baris atau kolom hanya membalikkan tanda-tanda. Saya membaca di suatu tempat, mungkin sehubungan dengan algoritma holografik yang diperkenalkan oleh Valiant, bahwa eliminasi Gaussian dapat dijelaskan dalam hal aksi kelompok dan ini pada gilirannya mengarah pada teknik generik dalam pengurangan kompleksitas.$\#P\mbox{-}hard$$NP\mbox{-}C$

Juga, saya merasa bahwa hampir semua sumber pengurangan kompleksitas untuk masalah komputasi adalah semacam simetri. Apakah itu benar Bisakah kita dengan keras memformalkan ini dalam teori kelompok?

Edit

Saya menemukan referensi . (hal 2, baris terakhir dari paragraf kedua). Saya tidak memahami makalah dengan benar, Jika pertanyaan saya didasarkan pada pemahaman yang salah tentang makalah, mohon koreksi saya.

Dalam kasus determinan, eliminasi Gaussian memang dapat dilihat setara dengan gagasan bahwa determinan memiliki kelompok simetri yang besar (dari bentuk tertentu) dan ditandai oleh kelompok simetri tersebut (artinya derajat homogen lain polinomial dalam n 2 variabel dengan simetri tersebut harus merupakan kelipatan skalar dari determinan). (Dan, mengenai poin @Tsuyoshi Ito bahwa simetri permanen tampaknya tidak membantu menghitungnya secara efisien: meskipun permanen juga ditandai oleh simetrinya, grup simetrinya jauh lebih kecil daripada determinannya.)$n$$n^2$

Anda dapat menemukan tulisan tentang ini - di mana simetri determinan digunakan untuk melakukan eliminasi Gaussian, di sepanjang jalan membuktikan bahwa determinan ditandai oleh simetrinya - dalam Proposisi 3.4.3 dari tesis saya (plug sendiri yang tidak tahu malu - tetapi juga, saya belum pernah melihatnya diutarakan dengan cara ini sebelumnya dan ditulis dengan detail penuh, seperti yang diminta OP, meskipun saya yakin itu sudah selesai; Saya akan senang jika seseorang memiliki referensi lain).

Mengenai gagasan bahwa simetri selalu mengarah pada pengurangan kompleksitas (atau tidak), di samping hal-hal yang sudah ada dalam komentar, lihat pertanyaan ini dan jawabannya.

Suatu hal yang menarik adalah bahwa dalam makalah Valiant pertama tentang apa yang sekarang dikenal sebagai versi Valiant tentang teori kompleksitas aljabar, ia mencoba untuk membuat titik bahwa salah satu alasan penentu adalah penting secara komputasi adalah karena secara kasar semua (maka) algoritma efisien yang diketahui bisa menjadi direduksi menjadi aljabar linier dan dari situ ke perhitungan determinan, misalnya algoritma FKT untuk menghitung kecocokan dalam grafik planar. Ini tentu saja berlebihan, tetapi terus dilakukan melalui penelitian ke dalam algoritma holografik, yang sering kali dikurangi untuk menghitung Pfaffian (kerabat dekat dari penentu). Tentunya Valiant tahu ini berlebihan, tapi inilah kutipan yang tepat hanya untuk memastikan saya tidak salah mengartikan ( L. Valiant. Kelengkapan kelas dalam aljabar. ACM STOC 1979 ):

Kesimpulan utama kami dapat diringkas secara kasar sebagai berikut:

(a) Aljabar linier pada dasarnya menawarkan satu-satunya teknik cepat untuk menghitung polinomial multivariat dengan derajat sedang

(b) ...

Ada kasus di mana simetri masalah (tampaknya) mencirikan kompleksitasnya. Salah satu contoh yang sangat menarik adalah kendala kepuasan masalah (CSP).

Definisi CSP

$U$$\Gamma$$k$$U^k$$\{0, 1\}$$V$$\Gamma$$\phi:V \rightarrow U$

Misalnya, dalam bahasa ini 3-SAT diberikan oleh $\Gamma$ yang merupakan himpunan semua disjungsi dari 3 literal, $U$ adalah secara sederhana $\{0, 1\}$. Untuk contoh lain, sistem persamaan linear mod 2 diberikan oleh a$\Gamma$ yang semuanya persamaan linear mod 2 dengan $k$ variabel, dan $U$ lagi $\{0, 1\}$.

Polimorfisme

Ada perasaan kekerasan CSP ditandai dengan simetri. Simetri yang dimaksud disebut polimorfisme. Sebuah polimorfisme adalah cara untuk lokal menggabungkan beberapa solusi untuk CSP untuk mendapatkan solusi baru. Secara lokal di sini berarti ada fungsi yang diterapkan ke masing-masing variabel secara terpisah. Lebih tepatnya, jika Anda memiliki beberapa solusi (tugas yang memuaskan)$\phi_1, \ldots, \phi_t$, polimorfisme adalah suatu fungsi $f:U^t \rightarrow U$ yang bisa diterapkan ke setiap variabel untuk mendapatkan solusi baru $\phi$: $\phi(v) = f(\phi_1(v), \ldots, \phi_t(v))$. For $f$ to be a polymorphism it should map all tuples of $t$ satisfying assignments to any instance to a satisfying assignment of the same instance.

A polymorphism for systems of linear equations for example is $f(x, y, z) = x + y + z \pmod 2$. Notice that $f(x, x, y) = f(y, x, x) = y$. An $f$ that satisfies this property is known as a Maltsev operation. CSPs that have a Maltsev polymorphism are solvable by Gaussian elimination.

On the other hand, disjunctions of 3 literals only have dictators as polymorphisms, i.e. functions of the type $f(x, y) = x$.

Polymorphisms and Complexity (the dichotomy conjecture)

Polymorphisms in fact have computational implications: if a CSP $\Gamma_1$ admits all polymorphisms of $\Gamma_2$, then $\Gamma_1$ is polynomial-time reducible to $\Gamma_2$. This is a way to formally say that a CSP $\Gamma_2$ which is "less symmetric" than another CSP $\Gamma_1$ is in fact harder.

A major open problem in complexity theory is to characterize the hardness of CSPs. The dichotomy conjecture of Feder and Vardi states that any CSP is either in P or NP-complete. The conjecture can be reduced to a statement about polymorphisms: a CSP is NP-hard if and only if the only polymorphisms it admits are "dictators" (otherwise it is in P). I.e. a CSP is hard only if there is no local way to form genuine new solutions from old solutions. The if part (hardness) is known, but the only if part (designing a polytime algorithm) is open.

However, an important case where we do have a dichotomy is boolean CSPs (where $U = \{0, 1\}$). According to Schaefer's theorem, a boolean CSP is in P if it admits one of 6 polymorphisms, otherwise it is NP-complete. The six polymorphisms are basically what you need to solve the problem either by gaussian elimination or by propagation (as you do with horn-sat for example), or to solve it by a trivial assignment.

To read more about polymorphisms, universal algebra, and the dichotomy conjecture, you can look at the survey by Bulatov.

Polymorphisms and Approximability

I also recommend an IAS lecture by Prasad Raghavendra where he puts his result giving optimal approximability of any CSP assuming the unique games conjecture in a similar framework. On a high level, if all polymorphisms (this needs to be generalized to handle approximation problems) of a CSP are close to dictators, one can use the CSP to design a way to test if a function is a dictator, and that turns out to be all you need in order to give a hardness of approximation reduction from unique games. This gives the hardness direction of his result; the algorithmic direction is that when a CSP has a polymorphism which is far from a dictator, one can use an invariance principle (generalization of central limit theorems) to argue that an SDP rounding algorithm gives a good approximation. A really sketchy intuition for the algorithmic part: a polymorphism that is far from a dictator doesn't care if it is given as arguments (a distribution over) variable assignments or gaussian random variables that locally approximate a distribution over variable assignments. This is the same way that a sum function "doesn't care" if it is given discrete random variables with small variance or gaussian r.v.'s with the same variance, by the central limit theorem. The gaussian random variables we need can be computed from an SDP relaxation of the CSP problem. So we find a polymorphism that is far from a dictator, feed it the gaussian samples, and get a good solution back.