Uma pergunta para a prova # P-completa da permanente de Ben-Dor / Halevi

14

No artigo de Ben-Dor / Halevi [1], é apresentada outra prova de que a permanente é -completa. Na parte posterior do documento, eles mostram a cadeia de redução enquanto o valor permanente é preservado ao longo da cadeia. Como o número de atribuições satiesfying de uma fórmula 3SAT pode ser obtido a partir do valor permanente, é suficiente calcular a permanente da matriz final . Por enquanto, tudo bem.#P

IntPermNoNegPerm2PowersPerm0/1-Perm
Φ0/1

No entanto, é sabido que a permanente de uma matriz é igual ao número de combinações perfeitas na capa dupla bipartida , ou seja, o gráfico da matriz . E esse número pode ser calculado com eficiência se for plano (usando o algoritmo de Kastelyens).0/1AG(0AAt0)G

Portanto, no total, isso significa que alguém poderia calcular o número de atribuições saties de uma fórmula booleana se o gráfico final for plano.ΦG

Como a incorporação de depende muito da fórmula , a esperança é que existam certas fórmulas que levam mais frequentemente a coberturas bipartidas planares. Alguém sabe se alguma vez foi investigado quão grandes são as chances de ser plano?GΦG

Como a contagem de soluções satiesfying é -completa, os gráficos serão quase sempre não-planos, mas não consigo encontrar nenhuma dica sobre esse tópico.#P

[1] Amir Ben-Dor e Shai Halevi. A permanente zero-one é # p-complete, uma prova mais simples. No 2º Simpósio de Israel sobre Teoria dos Sistemas de Computação, páginas 108-117, 1993. Natanya, Israel.

Etsch
fonte

Respostas:

11

Este tópico foi extensivamente investigado nos últimos anos sob o nome de algoritmos holográficos por pesquisadores como Valiant, Cai, Lu, Xia, Lipton e outros. Essencialmente, todos os casos tratáveis ​​de #CSP (contando problemas de satisfação com restrições) foram identificados em termos de teoremas da dicotomia (FP vs. # P-complete). Em particular, os cálculos da Matchgate foram identificados como a classe específica de problemas de contagem que se tornam tratáveis ​​em gráficos planares . Veja, por exemplo, este link para mais referências.

Martin Schwarz
fonte
1
Obrigado Martin pela resposta. O artigo que você vinculou vale a pena ler de qualquer maneira. No entanto, ele não menciona uma relação da forma . A matriz A e seu gráfico bipartido de capa dupla são aleatórios, mas dependem inteiramente da estrutura de e dos dispositivos gráficos usados. Portanto, a questão é mais sobre a classificação de fórmulas que levam a gráficos planares e quais não. (De fato, há fórmulas que serão planar, desde que implementado o algoritmo inteiro)ΦAGAGΦΦG
Etsch
2

Normalmente, um problema #CSP não ponderado é definido por um conjunto de relações e a entrada para o problema #CSP ( Γ ) é uma fórmula Φ .ΓΓΦ

Se contém apenas relações de aridade no máximo 1, e depois a cada entrada possíveis & Phi correspondes a um gráfico com gráficos estrela disjuntos, que é plana. Além disso, se Γ contém uma relação de aridade 2 ou mais, é fácil construir instâncias que não são planas. (Pense nas variáveis ​​como os vértices de um gráfico e nas restrições binárias como arestas entre esses vértices das variáveis. A aridade superior também contém trabalho. Dessa forma, qualquer gráfico pode ser construído, pelo menos como um subgrafo de outro gráfico.)ΓΦΓ

Em contraste, você está ignorando e perguntando diretamente sobre quais Φ levam a gráficos planares. No entanto, cada Φ define um gráfico (exclusivo). Não há incerteza, como você sugere neste parágrafo:ΓΦΦ

Como a incorporação de depende muito da fórmula Φ , a esperança é que existam certas fórmulas que levam mais frequentemente a coberturas bipartidas planares. Alguém sabe se alguma vez foi investigado quão grandes são as chances de G ser plano?GΦG

Tyson Williams
fonte