Beweis, dass TAUT coNP-vollständig ist (oder dass ein Problem coNP-vollständig ist, wenn sein Komplement NP-vollständig ist)

Ich muss beweisen, dass TAUT coNP-vollständig ist. Ich habe gezeigt, dass indem auf . Ich kann jedoch nicht herausfinden, wie ich beweisen kann, dass jedes Problem in coNP in Polynomzeit auf reduziert werden kann . Dazu würde ich eines von zwei Dingen brauchen:$\text{TAUT} \in \text{coNP}$$\text{SAT}$$\overline{\text{TAUT}}$$\text{TAUT}$

1. Ein bekanntes coNP-vollständiges Problem zur Reduktion oder
2. ein Beweis dafür, dass ein Problem coNP-vollständig ist, wenn sein Komplement NP-vollständig ist.

Keines davon wurde uns in einem Vortrag gegeben, daher kann ich nichts verwenden, ohne es selbst zu beweisen. Habe ich etwas verpasst, was offensichtlich sein sollte? Wo soll ich anfangen?

Ich davon aus, dass wir das Problem einer gegebenen DNF-Formel nennen und entscheiden, ob es sich um eine Tautologie handelt (wenn Sie sich nicht auf DNF beschränken möchten, funktioniert dies immer noch, da dies das Problem nur allgemeiner macht).$TAUT$

Die Antwort auf Ihre Fragen ergibt sich leicht aus der Definition von . Denken Sie daran , dass eine Sprache ist in ist . Zum Beispiel ist die Menge von DNF, die keine Tautologie sind. Um zu beweisen, dass ein DNF keine Tautologie ist, müssen Sie nur eine Zuordnung finden, die Ihrer Formel nicht entspricht. Dies kann in Polynomzeit mit einem NTM erfolgen (nur die Zuweisungen "bruteforce"). Daher ist es in . Mit anderen Worten, also .$coNP$$L \subseteq \{0,1\}^*$$coNP$$\bar{L} = \{x \in \{0,1\}^* \mid x \notin L\} \in NP$$\overline{TAUT}$$NP$$\overline{TAUT} \in NP$$TAUT \in coNP$

Nun nehmen Sie eine -komplette Sprache . Per Definition . Wir zeigen , dass ist -komplette, dass für jede Sprache ist , . Lassen Sie . Dann ist in . Durch -completeness von gibt es eine Funktion , berechenbare in Polynomzeit so dass iff . Dies entspricht der Aussage, dass iff$NP$$L$$\bar{L} \in coNP$$\bar{L}$$coNP$$A \in coNP$$A \leq \bar{L}$$A \in coNP$$\bar{A}$$NP$$NP$$L$$f$$x \in \bar{A}$$f(x) \in L$$x \notin \bar{A}$$f(x) \notin L$. Was wiederum wenn . Somit ist auch eine Reduktion von auf , was bedeutet, dass . Mit anderen Worten, ist vollständig.$x \in A$$f(x) \in \bar{L}$$f$$A$$\bar{L}$$A \leq \bar{L}$$\bar{L}$$coNP$

Nun, wenn Sie wollen zeigen , dass ist -komplette, müssen Sie nur zeigen , dass ist - vollständig. Und es ist nicht schwer zu erkennen, dass . In der Tat ist ein CNF erfüllbar, wenn , das ein DNF ist, keine Tautologie ist.$TAUT$$coNP$$\overline{TAUT}$$NP$$SAT \leq \overline{TAUT}$$F$$\neg F$