Hat Existenz von insgesamt

Es ist leicht zu erkennen, dass, wenn es insgesamt Suchprobleme gibt, die in der Polynomzeit nicht gelöst werden können (erstellen Sie ein Gesamtsuchproblem, indem Sie sowohl die Zeugen für die Mitgliedschaft als auch die Zeugen für die Nichtmitgliedschaft haben). $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$ $\mathsf{NP}$

Ist das Gegenteil auch wahr, dh

Bedeutet das Vorhandensein eines in der Polynomzeit nicht lösbaren Suchproblems, dass ? $\mathsf{NP}$ $\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}$

cc.complexity-theory reference-request search-problem Kaveh
quelle

Meinen Sie damit ein totales Suchproblem mit NP-Entscheidungsproblem? Ist die ganzzahlige Faktorisierung ein solches Problem?

Mohammad Al-Turkistany

Ich denke, er meint TFNP.

Domotorp

Antworten:

Ich gehe davon aus, dass P, NP und coNP in der Frage Klassen von Sprachen sind, keine Klassen von Versprechungsproblemen. In dieser Antwort verwende ich dieselbe Konvention. (Nur für den Fall, dass Sie über Klassen von Versprechungsproblemen sprechen, ist die Antwort positiv, da P = NP∩coNP als Klassen von Versprechungsproblemen gleichwertig mit P = NP ist.)

Dann ist die Antwort in einer relativierten Welt negativ.

Die Aussage TFNP ⊆ FP ist in der Literatur als Proposition Q bekannt [FFNR03]. Es gibt eine schwächere Aussage namens Proposition Q ' [FFNR03], wonach jede NPMV- Relation mit Ein-Bit-Antworten in FP ist. (Hier bedeutet eine Beziehung mit Ein-Bit-Antworten eine Teilmenge von {0,1} ^* × {0,1}.) Es ist leicht zu erkennen, dass Satz Q in Bezug auf ein Orakel Satz Q 'in Bezug auf dasselbe Orakel impliziert.

Fortnow und Rogers [FR02] untersuchten die Beziehungen zwischen der Aussage P = NP∩coNP, Proposition Q 'und einigen anderen verwandten Aussagen in relativierten Welten. Insbesondere impliziert Satz 3.2 (oder Satz 3.3) in [FR02], dass es ein Orakel gibt, in Bezug auf das P = NP∩coNP, aber Satz Q 'nicht gilt (und deshalb auch Satz Q nicht gilt). Daher impliziert P = NP∩coNP in einer relativierten Welt nicht Satz Q; oder indem man kontrapositiv nimmt, impliziert die Existenz einer TFNP-Beziehung, die nicht in Polynomzeit berechnet werden kann, nicht P ≠ NP∩coNP.

Verweise

[FFNR03] Stephen A. Fenner, Lance Fortnow, Ashish V. Naik und John D. Rogers. Auf Funktionen umkehren. Information and Computation , 186 (1): 90–103, Okt. 2003. DOI: 10.1016 / S0890-5401 (03) 00119-6 .

[FR02] Lance Fortnow und John D. Rogers. Trennbarkeit und Einwegfunktionen. Computational Complexity , 11 (3–4): 137–157, Juni 2002. DOI: 10.1007 / s00037-002-0173-4 .

Tsuyoshi Ito
quelle

Vielen Dank, Tsuyoshi. Es gibt auch ein Ergebnis in der Version Typ 2 des Problems, das zeigt, dass die Antwort dort nachweislich negativ ist: Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo und Toniann Pitassi, " The Relative Complexity of NP Search Problems ", 1998

Kaveh

Gibt es im Übrigen ein bekanntes Argument dafür, dass sie in der nicht-relativierten Welt nicht gleichwertig sind (basierend auf einigen Vermutungen in der Komplexitätstheorie oder Kryptographie)? Ich denke, wir sollten in der Lage sein, etwas basierend auf dem folgenden Kollisionsfindungsproblem zu sagen, das in TFNP vorliegt, aber seltsam erscheint, wenn es möglich wäre, es (auch mit zufälligen Reduktionen) auf ein TFUP-Problem zu reduzieren: gegeben eine Schaltung

, eine Kollision in finden

C : 2^{n + 1} \to 2^{n}

$C:2^{n+1}\to2^n$

C

$C$

Kaveh

@Kaveh: Ich bin mir nicht sicher, ob ich deine Frage im Kommentar verstehe. In der nicht-relativierten Welt kann man nur sagen, dass „P = NP andcoNP“ und „TFNP notFP“ nicht äquivalent sind, indem man zeigt, dass ersteres gilt und letzteres nicht, es sei denn, wir beweisen eine logische Unabhängigkeit Ergebnis. Die weit verbreitete Annahme ist jedoch, dass P P NP≠coNP, was impliziert, dass „P = NP∩coNP“ und „TFNP⊆FP“ gleichwertig sind (weil beide falsch sind). Daher weiß ich nicht, nach welcher Art von Vermutung Sie suchen.

Tsuyoshi Ito

Ich weiß nicht, ob es Sinn macht, aber ich dachte an etwas wie das Folgende: Das Suchproblem beim Auffinden von Kollisionen in einer Schaltung mit n + 1 Eingängen und n Ausgängen ist in

, jedoch wenn SPRNG existiert, ist es entsprechend Entscheidungsproblem (Zeuge extension) ist nicht in

T F N P

$\mathsf{TFNP}$

P^{N P \cap c o N P}

$\mathsf{P^{NP\cap coNP}}$

Kaveh

@Kaveh: Sprechen Sie über die Ungleichheit zwischen zwei Sätzen „P = NP∩coNP“ und „TFNP⊆FP“ oder über die Ungleichheit zwischen etwas anderem?

Tsuyoshi Ito

Für total UP lautet die Antwort ja, weil die Frage "Ist das i-te Bit der Lösung 1?" ist in . $NP \cap co-NP$

domotorp
quelle

Also

T F U P \neq F P ⟹ N P \cap c o N P \neq P ⟹ T F N P \neq F P

$\mathsf{TFUP} \neq \mathsf{FP}\implies \mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P} \implies \mathsf{TFNP} \neq \mathsf{FP}$

T F N P \neq F P ⟹ T F U P \neq F P

$\mathsf{TFNP} \neq \mathsf{FP} \implies \mathsf{TFUP} \neq \mathsf{FP}$

Ich kann nicht sagen, dass WIR es nicht wissen, aber ich weiß es bestimmt nicht. Wenn wir randomisierte Reduktionen zulassen, können Sie natürlich den Valiant-Vazirani-Trick ausführen, und die letzte Implikation wird auch wahr. (Es sei denn, ich irre mich ...)

Domotorp

F P

$\mathsf{FP}$

T F U P

$\mathsf{TFUP}$

T F N P

$\mathsf{TFNP}$

F P

$\mathsf{FP}$

Ja, perfekt.

Domotorp

Es scheint, dass der Valiant-Vazirani hier nicht funktioniert (oder zumindest sehe ich nicht, wie es funktioniert). Das Problem ist, dass das Ergebnis ein vielversprechendes Problem ist, zB SAT an USAT. Wir brauchen ein Problem ohne Versprechen. Und es scheint Gründe zu geben zu glauben, dass diese beiden nicht gleich sein sollten. Ich werde eine neue Frage zu TFNP und TFUP posten.

Kaveh