Schnittpunkt von Sprachen in NP

8

Kann der Schnittpunkt zweier Sprachen in NP, die nicht NP-vollständig sind, NP-vollständig sein?

Kann die Schnittmenge zweier Sprachen in coNP, die nicht coNP vollständig sind, coNP vollständig sein?

Kann der Schnittpunkt zweier Sprachen, eine in coNP, aber nicht vollständig, und eine andere in NP, aber nicht NP vollständig, NP vollständig oder coNP vollständig sein?

T ....
quelle
Sehr interessant. :)
Michael Wehar
2
Wenn P = NP, lautet die Antwort NEIN. In diesem Fall sind die einzigen Sprachen , die nicht NP-vollständig sind (coNP-complete) sind die leere Menge und . Σ
Gamow
3
Wenn P nicht gleich NP ist, gibt es bei den Zwischenleitern Probleme mit dem NP ... jedes Beispiel, das Sie für ein natürliches vorschlagen würden. Eins.
ARi

Antworten:

19

Nur ein erweiterter Kommentar, um ARis Kommentar besser zu erklären (ich habe ihn geschrieben, während ich ihn gesehen habe).

Es reicht aus, einen Ansatz mit "großer Lücke" zu verwenden, der dem im Satz von Lardner verwendeten ähnelt. zum Beispiel:

A1={xxSATf(|x|) is even}{xf(|x|) is odd}

A2={xxSATf(|x|) is odd}{xf(|x|) is even}

f

A1,A2A1A2=SAT

Marzio De Biasi
quelle
2
A1A2
{xxSATf(|x|) is even}A1PNPP=NP
Kannst du nicht nur über eine Polytime-Funktion sprechen?
ARi
@ARi: Nein, es muss langsam genug sein, um große Lücken zu schaffen, um die NP-Vollständigkeit zu verhindern (um eine verzögerte Diagonalisierung zu ermöglichen). Ich werde versuchen, in den nächsten Tagen einen formellen Beweis zu schreiben.
Marzio De Biasi
f