Pytanie do # P-kompletnego dowodu stałego z Ben-Dor / Halevi

W pracy Ben-Dor / Halevi [1] podano kolejny dowód na to, że stały jest -kompletny. W dalszej części artykułu pokazano łańcuch redukcji IntPerm ∝ NoNegPerm ∝ 2PowersPerm ∝ 0/1-Perm, podczas gdy wartość stała jest zachowana wzdłuż łańcucha. Ponieważ liczba satysfakcjonujących przypisań wzoru 3SAT $\#P$

$$\begin{equation} \text{IntPerm} \propto \text{NoNegPerm} \propto \text{2PowersPerm} \propto \text{0/1-Perm} \end{equation}$$ $\Phi$ można uzyskać z wartości stałej, wystarczy obliczyć stałą z końcowego -Matrix. Jak na razie dobrze.$0/1$

Jednakże jest dobrze wiadomo, że stałe o -Matrix A jest równa liczbie doskonałych skojarzeń z dwuczęściowego podwójnym opakowaniu G , to znaczy, na wykresie z matrycy ( 0 t 0 ) . I tę liczbę można obliczyć skutecznie, jeśli$0/1$$\text{A}$$G$$\begin{pmatrix} 0 & \text{A} \\ \text{A}^t & 0 \end{pmatrix}$ okaże się planarny (przy użyciu algorytmu Kastelyensa).$G$

W sumie oznacza to, że ktoś może obliczyć liczbę zadań satiesfying formuły boolowskiej jeśli ostateczny wykres$\Phi$ jest płaski.$G$

Ponieważ osadzanie zależy w dużej mierze od wzoru$G$ , istnieje nadzieja, że ​​istnieją pewne wzory, które częściej prowadzą do płaskich okładek dwustronnych. Czy ktoś wie, czy kiedykolwiek badano, jak duże są szanse$\Phi$ będzie płaski?$G$

Ponieważ liczenie rozwiązań satiesfying jest -kompletne, wykresy na pewno prawie zawsze są niepłaskie, ale nie mogę znaleźć żadnych wskazówek dotyczących tego tematu.$\#P$

[1] Amir Ben-Dor i Shai Halevi. Zero-one permanent jest # p-complete, prostszy dowód. W 2nd Israel Symposium on Theory of Computing Systems, strony 108-117, 1993. Natanya, Izrael.

Temat ten został szeroko zbadany w ostatnich latach pod nazwą algorytmów holograficznych przez badaczy takich jak Valiant, Cai, Lu, Xia, Lipton i inni. Zasadniczo wszystkie możliwe do leczenia przypadki #CSP (liczenie problemów satysfakcji z ograniczeń) zostały zidentyfikowane w kategoriach twierdzeń dychotomii (FP vs. # P-complete). W szczególności obliczenia Matchgate zostały zidentyfikowane jako szczególna klasa problemów z liczeniem, które można rozwiązać na wykresach płaskich . Zobacz np. Ten link, aby uzyskać dodatkowe odniesienia.

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

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

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

$G$$\Phi$$G$