Kann ich die Kardinalität eines Sets begrenzen, wenn bekannt ist, dass die Prüfung auf Mitgliedschaft NP-vollständig ist?

Ich möchte eine Grenze für die Kardinalität des Satzes von Einheitsscheibendiagrammen mit Eckpunkten haben. Es ist bekannt, dass die Überprüfung, ob ein Graph Mitglied dieser Menge ist, NP-schwer ist. Führt dies zu einer Untergrenze der Kardinalität unter der Annahme von P NP? $N$ $\neq$

Angenommen, es gibt eine Reihenfolge für alle Diagramme mit Eckpunkten. Würde die NP-Härte dann bedeuten, dass die Kardinalität überschreitet , da Sie sonst die Mitgliedschaft in der Polynomzeit durch eine binäre Suche durch die Menge testen könnten? Ich denke, dies würde voraussetzen, dass Sie das Set irgendwie im Speicher gespeichert haben ... Ist das erlaubt? $N$ $2^N$

Definition: Ein Diagramm ist ein Einheitsscheibendiagramm, wenn jeder Scheitelpunkt einer Einheitsscheibe in der Ebene zugeordnet werden kann, sodass Scheitelpunkte immer dann verbunden werden, wenn sich ihre Scheiben schneiden.

Hier ist eine Referenz zur NP-Härte von Mitgliedschaftstests für Unit-Disk-Diagramme: http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf

cc.complexity-theory graph-theory David Choi
quelle

Ich frage mich, gibt es ein Beispiel, bei dem diese Technik die bekannteste Untergrenze für die Größe eines Satzes liefert? Das wäre eine coole indirekte kombinatorische Anwendung der Komplexitätstheorie.

Sasho Nikolov

Danke für Ihre freundliche Unterstützung. Beide Antworten waren hilfreich und aufschlussreich; Ich hätte beides ohne das andere akzeptiert.

David Choi

Antworten:

Ich bin mir nicht sicher, ob Sie diese Frage für die Technik oder für die Antwort stellen, aber es gibt ein kürzlich veröffentlichtes Papier von McDiarmid und Mueller, in dem die Anzahl der (beschrifteten) Einheitsscheibendiagramme auf Eckpunkten beträgt ; siehe http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf . $n$ $2^{(2 + o(1))n}$

Bart Jansen
quelle

Mahaneys Theorem besagt, dass spärliche NP-vollständige Mengen existieren, wenn P = NP ist. Unter der Annahme, dass eine superpolynomielle Untergrenze für die Anzahl der Instanzen der Größe in vollständigen Mengen für unendlich viele impliziert . Das heißt, wenn , dann muss jede vollständige Menge ein so dass für unendlich viele ganze Zahlen die Menge mindestens Saiten der Länge . $P \neq NP$ $n$ $NP$ $n$ $P \neq NP$ $NP$ $\epsilon \gt 0$ $n\ge 0$ $2^{n^{\epsilon}}$ $n$

H. Buhrman und JM Hitchcock haben bewiesen, dass die Untergrenze ( ) eng ist, es sei denn, die Polynomhierarchie bricht zusammen. $2^{n^{\epsilon}}$

[1] H. Buhrman und JM Hitchcock, NP-Hard-Sets sind exponentiell dicht, es sei denn, coNP ⊆ NP / poly, In IEEE Conference on Computational Complexity, S. 1–7, 2008

[2] Eric Allender, Ein Statusbericht zur Frage P versus NP, Fortschritte bei Computern, Band 77, 2009, Seiten 117-147

Mohammad Al-Turkistany
quelle

[Mah82] SR Mahaney. Sparse komplette Sätze für NP: Lösung einer Vermutung von Berman und Hartmanis , Journal of Computer and System Sciences 25: 130-143, 1982.

Marzio De Biasi

Jeder NP-vollständige Satz hat zählbar unendliche Kardinalität. Sie haben wahrscheinlich gemeint, dass P ≠ NP eine superpolynomielle Untergrenze für die Anzahl der Instanzen der Größe für unendlich viele impliziert . Beachten Sie auch, dass superpolynomisch ist, ohne die von Ihnen angegebene Form zu haben.

n

$n$

n

$n$

2^{(\log n)^{2}}

$2^{(\log n)^2}$

András Salamon

Danke András, dein Kommentar ist in der Antwort enthalten.

Mohammad Al-Turkistany

@Mohammad: mache die Untergrenze oder : das bedeutet Superpolynom.

2^{ω (\log n)}

$2^{\omega(\log n)}$

n^{ω (1)}

$n^{\omega(1)}$

Sasho Nikolov

@Sasho, H. Buhrman und JM Hitchcock haben die Untergrenze ( ) bewiesen, die ich in meiner Antwort erwähnt habe, es sei denn, die Polynomhierarchie bricht zusammen. H. Buhrman und JM Hitchcock, NP-harte Mengen sind exponentiell dicht, es sei denn, coNP ⊆ NP / poly, In IEEE-Konferenz über Computerkomplexität, Seiten 1–7, 2008

2^{n^{ϵ}}

$2^{n^{\epsilon}}$

Mohammad Al-Turkistany