Ist $ sat $ $ NP $ -Hard?

Question

Ich suche einen $ NP $ -hardness-Beweis für die folgende Variante von $ SAT $ :

$$ Sogar Sat={\ Langle \ phi \ Rangle: \ phi \ text {hat eine gerade Anzahl der erfüllenden Zuordnungen} \} $$

Ich habe seit einiger Zeit mit Gadgets herumgespielt, aber ich konnte keine Reduzierung erstellen.Trotzdem fühle ich mich, als sollte es einen geben.Hilfe!

Answer 1

$ \ textsf {Evensat} $ ist $ \ oplus p $ -complete (ausgesprochen "Parität $ P $ "). Der Weg, dies zu sehen, ist (i), dass es die Ergänzung von $ \ textsf {Oddsat} $ , die "die" natürliche $ \ oplus p $ -Complete-Problem auf dieselbe Weise $ \ textsf {Sat} $ ist" die "natürliche $ \ Mathcal {NP} $ -complete Problem, und (ii) $ \ oplus p $ ist unter Ergänzung geschlossen.

Der Valiant-Vazirani-Theorem ergibt eine randomisierte Kochreduzierung (dh eine Reduzierung von vielen eins) mit einer einseitigen Fehlerwahrscheinlichkeit von $ \ Mathcal {O} (1 / N ) $ von $ \ textsf {SAT} $ bis $ \ textsf {Evensat} $ . Das heißt, $ \ textsf {Evensat} $ ist $ \ Mathcal {NP} $ -hard unter randomisiert Reduzierungen. Deshalb wird der Valiani-Vazirani-Theorem normalerweise als $ \ Mathcal {NP} \ Subseteq \ Mathcal {RP} ^ {\ oplus p} $ . .

wir haben $ \ matcal {rp ^ ^ {\ oplus p} \ subseteq p ^ {\ # p} $ , so ist der Satz von VV ein bisschen enger als Was würden Sie von Todas Theorem bekommen?

Es ist unwahrscheinlich, dass $ \ textsf {Evensat} $ $ \ Mathcal {NP} $ ist> -Complete, denn dann bricht die Polynomhierarchie auf die erste Ebene zusammen, $ pH= NP $ . Es ist eine offene Frage, ob $ NP $ und $ \ oplus p $ vergleichbar ist, bis jetzt es gibt nur Oracle-Beweise, dass sie unvergleichlich sind. (Ich weiß nicht, ob es im Allgemeinen überwiesen ist, dass Valiant-Vazirani von $ \ Mathcal {NP} \ Subseteq \ Mathcal {RP} ^ {\ oplus p} $ < / span> bis $ \ Mathcal {NP} \ Subseteq \ Mathcal {P} ^ {\ oplus p} $ . In diesem Fall ist seit $ P ^ {\ oplus p}=oplus p $ , wir hätten $ \ mathcal {np} \ subseticq \ oplus p $ . Wenn ich [1] richtig gelesen habe, dann ist es nicht allgemein übertragbar, da es die Polynomhierarchie zusammenbrechen würde)

[1] dell, holger et al. "Ist die Isolationswahrscheinlichkeit von Valiant-Vazirani verbessert?" Rechenkomplexität 22.2 (2013): 345-383.

Answer 2

Es ist bekannt, dass $ NP \ Subset P ^ {\ # p} $ nach TODA-Satzung, aber jetzt ist Ihre Frage "NP-Hardnes von sogar Sat"ein offenes Problem. Wir wissen, dass $ NP \ Subset BPP ^ {mod_2 SAT} $