Una pregunta a la prueba # P-completa del permanente de Ben-Dor / Halevi

En el documento de Ben-Dor / Halevi [1] se da otra prueba de que el permanente es -completo. En la parte posterior del documento, muestran la cadena de reducción mientras el valor permanente se conserva a lo largo de la cadena. Como el número de asignaciones satisfactorias de una fórmula 3SAT se puede obtener del valor permanente, es suficiente calcular el permanente de la matriz final . Hasta aquí todo bien.$\#P$

Sin embargo, es bien sabido que el permanente de una matriz es igual al número de coincidencias perfectas en la doble cubierta bipartita , es decir, el gráfico de la matriz . Y este número se puede calcular de manera eficiente si resulta ser plano (usando el algoritmo Kastelyens).$0/1$$\text{A}$$G$$\begin{pmatrix} 0 & \text{A} \\ \text{A}^t & 0 \end{pmatrix}$$G$

Entonces, en total, esto significa que alguien podría calcular el número de asignaciones satisfactorias de una fórmula booleana si el gráfico final es plano.$\Phi$$G$

Dado que la incrustación de depende en gran medida de la fórmula , la esperanza es que existan ciertas fórmulas que conducen con mayor frecuencia a cubiertas bipartitas planas. ¿Alguien sabe si alguna vez se ha investigado qué tan grandes son las posibilidades de que sea ​​plano?$G$$\Phi$$G$

Dado que el conteo de soluciones satisfactorias es -completo, las gráficas serán casi siempre no planas, pero no puedo encontrar ninguna pista sobre este tema.$\#P$

[1] Amir Ben-Dor y Shai Halevi. Cero uno permanente es # p-completo, una prueba más simple. En el 2º Simposio de Israel sobre Teoría de Sistemas Informáticos, páginas 108-117, 1993. Natanya, Israel.

Este tema ha sido ampliamente investigado en los últimos años bajo el nombre de Algoritmos Holográficos por investigadores como Valiant, Cai, Lu, Xia, Lipton y otros. Esencialmente, todos los casos manejables de #CSP (problemas de satisfacción de restricciones de conteo) se han identificado en términos de teoremas de dicotomía (FP vs. # P-complete). En particular, los cálculos de Matchgate se han identificado como la clase específica de problemas de conteo que se vuelven manejables en gráficos planos . Consulte, por ejemplo, este enlace para obtener más referencias.

$\Gamma$$\Gamma$$\Phi$

$\Gamma$$\Phi$$\Gamma$

$\Gamma$$\Phi$$\Phi$

$G$$\Phi$$G$