Zählen Sie die Reduzierung von #SAT auf #HornSAT?

Ist es möglich, eine Reduzierung der Zählung von #SAT auf #HornSAT zu finden? Ich habe diese Frage hier nicht gefunden und habe mich daher entschlossen zu prüfen, ob jemand eine Antwort darauf hat. Lassen Sie mich erklären, was ich mit Reduktion zähle.

Angenommen, sind zwei Zählprobleme. Zum Beispiel fragt #SAT, wie viele erfüllbare Zuweisungen für eine bestimmte Instanz vorhanden sind ϕ , und f , g sind ähnliche Zählprobleme, wenn die Gesamtzahl der Zeugen ermittelt wird. Eine schwach sparsame Zählreduktion von f auf g besteht aus einem Paar von polynomialzeitberechnbaren Funktionen σ : { 0 , 1 } ∗ → { 0 , 1 $f,g : \{0,1\}^* \to \mathbb N$$\phi$$f,g$$f$$g$ und τ : { 0 , 1 } ∗ × N → N, so dass f ( x ) = τ ( x , g ( σ ( x ) ) ) . In dem Fall, dass f ( x ) = g ( σ ( x ) ) ist , ist dies als stark sparsame Zählreduktion bekannt.$\sigma : \{0,1\}^* \to \{0,1\}^*$$\tau : \{0,1\}^* \times \mathbb N \to \mathbb N$$f(x) = \tau (x, g(\sigma(x)))$$f(x) = g(\sigma(x))$

Ich kann sehen, dass wenn es eine solche Reduzierung der Zählung von #SAT auf #HornSAT gibt, dies eine schwach sparsame Reduzierung sein muss: Eine starke Reduzierung würde bedeuten, dass die Instanzen #SAT und #HornSAT zusammen keine oder eine Anzahl von Lösungen ungleich Null haben. und unter der Annahme, dass , ist dies unmöglich (als HornSAT ∈ P, während SAT N P -voll ist).$\mathsf P \ne \mathsf{NP}$$\in \mathsf P$$\mathsf{NP}$

Meine Frage ist also: Gibt es eine schwach sparsame Zählreduktion von #SAT auf #HornSAT? Wenn ja, kann mir bitte jemand einen Hinweis geben?

$\phi$$\psi$