Eliminação gaussiana em termos de ação em grupo

13

A eliminação gaussiana torna determinante do tempo polinomial da matriz computável. A redução da complexidade na computação do determinante, que é a soma dos termos exponenciais, é devida à presença de sinais negativos alternativos (a falta de qual torna a computação permanente é isto é, mais difícil que o problemas ). Isso leva a algum tipo de simetria determinante, por exemplo, a troca de um par de linhas ou colunas apenas inverte os sinais. Li em algum lugar, provavelmente em conexão com os algoritmos holográficos introduzidos por Valiant, que a eliminação gaussiana poderia ser explicada em termos de ação em grupo e isso, por sua vez, leva a técnicas genéricas de redução da complexidade.N P - C#P-hardNP-C

Além disso, sinto que quase todas as fontes de redução de complexidade para qualquer problema computacional são algum tipo de simetria presente. É verdade? Podemos formalizar isso rigorosamente em termos de teoria de grupos?

Editar

Eu encontrei a referência . (página 2, última linha do segundo parágrafo). Não entendi o documento corretamente. Se minha pergunta é baseada no entendimento errado do documento, corrija-me.

DurgaDatta
fonte
3
Minha opinião pessoal sobre o segundo parágrafo: problemas de grande interesse geralmente têm simetria, tenham algoritmos eficientes ou não. Mas, além disso, não vejo a verdade em seu sentimento de que "quase toda fonte de redução de complexidade para qualquer problema computacional seja algum tipo de simetria presente". Por exemplo, não vejo qual simetria o algoritmo de Kruskal usa. Além disso, a visão de que algoritmos eficientes surgem da simetria em problemas não parece explicar por que a simetria da permanente aparentemente não ajuda a computá-la com eficiência.
Tsuyoshi Ito
4
Não, a simetria nem sempre diminui a complexidade. Toda pergunta interessante sobre grupos é indecidível. A classificação não é.
Jeffε
2
a declaração formal mais próxima nessa direção que vem à mente é a conjectura algébrica da dicotomia, que (para dizer muito vagamente) afirma que um CSP está em P se e somente se houver maneiras não triviais de combinar duas soluções em uma terceira solução genuinamente diferente . um exemplo é a solução de um sistema de modificação linear 2, que é solúvel por eliminação de Gauss, e onde duas soluções diferentes determinar um subespaço afim de soluções
Sasho Nikolov
2
ah, então o que você realmente está falando é o TCG, que parte da ideia de que o problema permanente x determinante pode ser entendido em termos (aproximadamente) das simetrias sob as quais as duas funções são invariantes.
Sasho Nikolov 29/08/2012
2
Há muitas razões pelas quais um problema admite um algoritmo eficiente. Convexidade, submodularidade, etc. As simetrias causam explosão de casos em alguns problemas combinatórios e às vezes são vistas como uma fonte de ineficiência.
Vijay D

Respostas:

12

No caso do determinante, a eliminação gaussiana pode de fato ser vista como equivalente à idéia de que o determinante possui um grande grupo de simetria (de uma forma particular) e é caracterizado por esse grupo de simetria (significando qualquer outro grau homogêneo polinomial em variáveis ​​com essas simetrias devem ser um múltiplo escalar do determinante). (E, como no argumento de Tsuyoshi Ito, as simetrias da permanente parecem não ajudar a calculá-la com eficiência: embora a permanente também seja caracterizada por suas simetrias, seu grupo de simetria é muito menor que o do determinante.)n 2nn2

Você pode encontrar um resumo disso - em que as simetrias do determinante são usadas para eliminar a eliminação gaussiana, provando que o determinante é caracterizado por suas simetrias - na Proposição 3.4.3 da minha tese (vergonhoso auto plug - mas além disso, nunca o vi redigido dessa maneira antes e escrito em todos os detalhes, como o OP pedia, embora eu tenha certeza de que foi feito; ficaria feliz se alguém tivesse outras referências).

Quanto à ideia de que a simetria sempre leva à redução da complexidade (ou não), além das coisas já mencionadas nos comentários, veja esta pergunta e suas respostas.

Um ponto interessante é que, nos primeiros trabalhos de Valiant sobre o que agora é conhecido como versão da teoria da complexidade algébrica de Valiant, ele estava tentando argumentar que uma das razões pelas quais o determinante é importante computacionalmente é porque aproximadamente todos os algoritmos eficientes (então) conhecidos poderiam ser reduzido a álgebra linear e, portanto, à computação do determinante, por exemplo, o algoritmo FKT para contagem de correspondências em gráficos planares. É claro que isso é um exagero, mas continua a ser confirmado pela pesquisa de algoritmos holográficos, que muitas vezes se reduzem à computação do Pfaffian (um parente próximo do determinante). Certamente Valiant sabia que isso era um exagero, mas aqui está a citação exata apenas para garantir que eu não esteja deturpando ( L. Valiant. Classes de completude em álgebra. ACM STOC 1979 ):

Nossas principais conclusões podem ser resumidas da seguinte forma:

(a) A álgebra linear oferece essencialmente a única técnica rápida para calcular polinômios multivariados de grau moderado

b) ...

Joshua Grochow
fonte
7

Há casos em que as simetrias de um problema (parecem) caracterizam sua complexidade. Um exemplo muito interessante são os problemas de satisfação com restrições (CSPs).

Definição de CSP

UΓkUk{0,1}VΓϕ:VU

ΓU{0,1}ΓkU{0,1}

Polimorfismos

ϕ1,,ϕtf:UtUϕϕ(v)=f(ϕ1(v),,ϕt(v))ft

Um polimorfismo para sistemas de equações lineares, por exemplo, é . Observe que . Um que satisfaça essa propriedade é conhecido como operação de Maltsev. CSPs que possuem um polimorfismo de Maltsev são solucionáveis ​​por eliminação gaussiana.f ( x , x , y ) = f ( y , x , x ) = y ff(x,y,z)=x+y+z(mod2)f(x,x,y)=f(y,x,x)=yf

Por outro lado, as disjunções de 3 literais só têm ditadores como polimorfismos, ou seja, funções do tipo .f(x,y)=x

Polimorfismos e Complexidade (a conjectura da dicotomia)

De fato, os polimorfismos têm implicações computacionais: se um CSP admite todos os polimorfismos de , é redutível em tempo polinomial para . Essa é uma maneira de dizer formalmente que um CSP "menos simétrico" que outro CSP é de fato mais difícil.Γ 2 Γ 1 Γ 2 Γ 2 Γ 1Γ1Γ2Γ1Γ2Γ2Γ1

Um grande problema em aberto na teoria da complexidade é caracterizar a dureza dos CSPs. A conjectura de dicotomia de Feder e Vardi afirma que qualquer CSP está em P ou NP completo. A conjectura pode ser reduzida a uma afirmação sobre polimorfismos: um CSP é NP-difícil se e somente se os únicos polimorfismos que admite são "ditadores" (caso contrário, é em P). Ou seja, um CSP é difícil apenas se não houver uma maneira local de formar novas soluções genuínas a partir de soluções antigas. A parte if (dureza) é conhecida, mas a única parte if (projetando um algoritmo polytime) está aberta.

No entanto, um caso importante em que temos uma dicotomia são os CSPs booleanos (onde ). De acordo com o teorema de Schaefer , um CSP booleano está em P se admitir um dos 6 polimorfismos, caso contrário, é NP completo. Os seis polimorfismos são basicamente o que você precisa para resolver o problema por eliminação gaussiana ou por propagação (como você faz com horn-sat, por exemplo), ou para resolvê-lo por uma atribuição trivial.U={0,1}

Para ler mais sobre polimorfismos, álgebra universal e a conjectura de dicotomia, você pode ver a pesquisa de Bulatov .

Polimorfismos e aproximabilidade

Eu também recomendo uma palestra do IAS de Prasad Raghavendra onde ele coloca seu resultadofornecendo uma ótima aproximação de qualquer CSP, assumindo a conjectura de jogos exclusivos em uma estrutura semelhante. Em um nível alto, se todos os polimorfismos (que precisam ser generalizados para lidar com problemas de aproximação) de um CSP estão próximos dos ditadores, pode-se usar o CSP para projetar uma maneira de testar se uma função é um ditador, e isso resulta em seja tudo o que você precisa para reduzir a dureza da aproximação em jogos únicos. Isso fornece a direção da dureza de seu resultado; a direção algorítmica é que quando um CSP tem um polimorfismo que está longe de ser um ditador, pode-se usar um princípio de invariância (generalização de teoremas de limite central) para argumentar que um algoritmo de arredondamento SDP fornece uma boa aproximação. Uma intuição realmente superficial para a parte algorítmica: um polimorfismo que está longe de ser um ditador não não importa se é dado como argumentos (uma distribuição sobre) atribuições de variáveis ​​ou variáveis ​​aleatórias gaussianas que aproximam localmente uma distribuição sobre atribuições de variáveis. É da mesma maneira que uma função de soma "não se importa" se receber variáveis ​​aleatórias discretas com pequena variação ou RV gaussianos com a mesma variação, pelo teorema do limite central. As variáveis ​​aleatórias gaussianas de que precisamos podem ser calculadas a partir de um relaxamento do problema de CSP no SDP. Então, encontramos um polimorfismo que está longe de ser um ditador, alimentamos as amostras gaussianas e obtemos uma boa solução de volta. se receber variáveis ​​aleatórias discretas com pequena variância ou RV gaussianos com a mesma variância, pelo teorema do limite central. As variáveis ​​aleatórias gaussianas de que precisamos podem ser calculadas a partir de um relaxamento do problema de CSP no SDP. Então, encontramos um polimorfismo que está longe de ser um ditador, alimentamos as amostras gaussianas e obtemos uma boa solução de volta. se receber variáveis ​​aleatórias discretas com pequena variância ou RV gaussianos com a mesma variância, pelo teorema do limite central. As variáveis ​​aleatórias gaussianas de que precisamos podem ser calculadas a partir de um relaxamento do problema de CSP no SDP. Então, encontramos um polimorfismo que está longe de ser um ditador, alimentamos as amostras gaussianas e obtemos uma boa solução de volta.

Sasho Nikolov
fonte
2
Bulatov também deu uma convidou conversa sobre sua pesquisa na CSR 2011.
Tyson Williams