in

26

Die Untersuchung der prägnanten Darstellung von Graphen wurde von Galperin und Wigderson in einem Artikel von 1983 initiiert , in dem sie nachweisen, dass für viele einfache Probleme wie das Finden eines Dreiecks in einem Graphen die entsprechende prägnante Version in vollständig ist. Papadimitriou und Yanakkakis forcieren diese Forschungslinie und beweisen, dass für ein Problem das -complete / -complete ist, die entsprechende Kurzfassung, nämlich Succinct , -complete und -complete. (Sie zeigen auch , dass , wenn ist Π N P P Π N E X P E X P Π N L Π P S P A C ENPΠNPPΠNEXPEXPΠNL-komplette, dann Prägnante ist -komplette.ΠPSPACE

Nun ist meine Frage, gibt es irgendwelche Probleme , für die bekannt ist, die entsprechende Kurzfassung befindet sich in ? Mich würde interessieren, welche anderen verwandten Ergebnisse (sowohl positive als auch Unmöglichkeitsergebnisse, falls vorhanden) ich möglicherweise oben verpasst habe. (Ich konnte bei einer Google-Suche nichts Interessantes finden, da Suchwörter wie Prägnanz, Repräsentation, Probleme, Grafiken zu fast jeder Komplexität führen! :))PΠP

Nikhil
quelle
was für ein problem suchst du Sicher bleiben einige triviale Grapheneigenschaften auch in der prägnanten Version trivial, z. B. die Eigenschaft, die von jedem Graphen erfüllt wird, sowie die Eigenschaft, die von keinem Graphen erfüllt wird. Vielleicht suchen Sie eine andere Immobilie als diese beiden?
Sasho Nikolov
2
Zunächst möchte ich erwähnen, dass die Ergebnisse von Papadimitriou und Yannakakis für eine besondere Art der Reduktion Vollständigkeit erfordern. (Dennoch kann ihr Ergebnis auf eine Vielzahl von Problemen angewendet werden.)
Bruno
2
Nun zu Ihrer Frage: Da die Komplexität der prägnanten Version eines Problems (im Allgemeinen) exponentiell ansteigt, würde dies wahrscheinlich bedeuten, dass Ihr ursprüngliches Problem in logarithmischer Zeit lösbar ist? Aber dann kann ein in logarithmischer Zeit lösbares Problem tatsächlich in konstanter Zeit gelöst werden. Daher kann die prägnante Version auch in konstanter Zeit gelöst werden. Ich bin ziemlich davon überzeugt, dass mein oben genanntes "Argument" zu viele Lücken aufweist, um völlig korrekt zu sein, aber es bedeutet zumindest, dass Ihre Probleme am Anfang sehr speziell sein müssen.
Bruno
@SashoNikolov Natürlich bin ich auf der Suche nach nicht trivialen Graphenigenschaften. Ich fand es anfangs ziemlich überraschend, dass die Überprüfung, ob ein Graph ein Dreieck hat, -vollständig wäre! Wenn Sie das Problem in Betracht ziehen, festzustellen , ob eine Eingabezeichenfolge eine ist dies genau das Problem der Schaltungserfüllbarkeit in der Succint-Welt. Dieses spezielle Beispiel hat mich zu der Überlegung veranlasst, ob es ein Problem geben kann, dessen Succint-Version in P. 1NP1
Nikhil,
@Bruno Ich habe nach den gleichen Grundsätzen gedacht, konnte mir aber noch kein konkretes Beispiel einfallen lassen!
Nikhil

Antworten:

16

Hier ist ein interessantes Problem, dessen prägnante Version interessante Eigenschaften hat. Definieren Sie Circuit-Size- als Problem: Hat diese Funktion bei einer Booleschen Funktion als Bit-String eine Circuit-Size von höchstens ? Beachten Sie, dass dieses Problem in .2 n 2 n / 2 N P2n/22n2n/2NP

Eine Möglichkeit zur Definition der Kurzschlussgröße wäre: Für eine Konstante wollen wir bei gegebenem Eingang und Größe der Schaltung wissen, ob ihre Wahrheitstabelle eine Instanz ist of Circuit-Size- . Dies ist jedoch ein triviales Problem: Alle Eingänge, bei denen es sich um tatsächliche Schaltkreise handelt, sind Ja-Instanzen. So ist dieses Problem in . k n n k C 2 n / 2 P2n/2knnkC2n/2P

Ein allgemeinerer Weg, um die Kurzschlussgröße wäre: Wir erhalten einen beliebigen Kreis und möchten wissen, ob seine Wahrheitstabelle eine Instanz der Kreisgröße . Aber wenn die Anzahl der Eingaben in , die Größe von ist und , können wir automatisch annehmen: Die Eingabe selbst ist ein Zeuge für die Sprache. Ansonsten haben wir . In diesem Fall ist die Eingabelänge bereits sehr groß, sodass wir alle möglichen Zuweisungen in ausprobieren können. C 2 n / 2 n C m C m 2 n / 2 m 2 n / 2 m 2 n m O ( 1 ) N P N P N P2n/2C2n/2nCmCm2n/2m2n/2m2nmO(1)Holen Sie sich die Wahrheitstabelle der Funktion, und jetzt kehren wir wieder zum ursprünglichen Problem zurück. Das ist also ein Problem in dessen prägnante Version auch in .NPNPNP

Es wird angenommen, dass dieses Problem nicht hart ist; siehe das Papier von Kabanets und Cai (http://www.cs.sfu.ca/~kabanets/Research/circuit.html)NP

Ryan Williams
quelle
2
Das ist sehr schön und zerreißt jede Intuition, die ich dachte, ich hätte ..
Sasho Nikolov
12

Angesichts der Tatsache, dass selbst die Entscheidung, ob der durch eine bestimmte prägnante Darstellung dargestellte Graph mindestens eine Kante enthält oder nicht, dem Schaltkreis SAT entspricht und daher NP-vollständig ist, ist es verlockend zu behaupten, dass jede interessante Eigenschaft einer prägnanten Darstellung NP-schwer sein sollte eine passende Definition von „interessant“. Diese Behauptung wäre ein komplexitätstheoretisches Analogon zum Satz von Rice . Leider ist das Finden des allgemeinsten komplexitätstheoretischen Analogons von Rices Theorem ein offenes Problem , obwohl es Ergebnisse gibt, die einige Formen solcher komplexitätstheoretischer Analoga ergeben.

Tsuyoshi Ito
quelle
Danke für den Hinweis! Das war eine großartige Antwort von Russell auf die Frage, die Sie verlinkt haben!
Nikhil
9

Ich wollte nicht, dass dies eine Antwort ist, aber es wären zu viele Kommentare erforderlich. Hoffe es ist nützlich.

Wie Tsuyoshi betont, ist es verlockend zu vermuten, dass alle "nicht-trivialen" Eigenschaften hart sind (zum Beispiel NP-hart). Um dies zu zeigen, müssen Sie jedoch nicht-trivial definieren. In Rices Theorem sind die nichttrivialen Eigenschaften alle Eigenschaften mit Ausnahme der Eigenschaft, die alle rechnerisch aufzählbaren Sprachen enthält, und der Eigenschaft, die keine rechnerisch aufzählbare Sprache enthält. Es ist weniger klar, was die richtige Definition von Nicht-Trivialität für prägnante Probleme ist. Definitiv sind die Eigenschaften, die alle Zeichenfolgen oder keine Zeichenfolgen enthalten, in P. Aber es gibt auch andere in P. Beispielsweise die Eigenschaft , die Zeichenfolgen entspricht, deren mittleres Bit 0 ist. Oder enthält alle Zeichenfolgen mit Bits, sodass jedes te Bit 1 ist& Pgr; 2 n 2 n / x x = n O ( 1 )ΠΠ2n2n/xx=nO(1) . Wie definieren wir "trivial", um diese Art von Eigenschaften zu erfassen?

Eine Idee ist, sich die anzuschauen, die "symmetrisch" sind: Wenn sich ein String in , befindet sich auch jede Permutation der Bits von in . Solche Eigenschaften hängen nur von der Anzahl von 1 Bit in einer Zeichenfolge ab. In einer Antwort auf die mit Tsuyoshi verknüpfte Frage gibt Ryan Williams einen Link zu diesem Artikel, der zeigt, dass all diese Probleme UP-schwer sind.s Π s ΠΠsΠsΠ

Andere Ideen, wie man "nicht-triviales Eigentum" definiert? Wir können als eine Familie von Booleschen Funktionen betrachten (die Indikatorfunktionen der Eigenschaft für jede Zeichenkettenlänge). Es scheint mir, dass die nicht-trivialen Eigenschaften diejenigen sind, für die die entsprechende Familie von Booleschen Funktionen eine nicht-triviale Komplexität aufweist. Können wir zum Beispiel zeigen, dass Eigenschaften, deren zugeordnete boolesche Funktionsfamilie eine lineare Entscheidungsbaumkomplexität aufweist, schwierig sind?Π

Sasho Nikolov
quelle
1
In Rices Theorem ist der Schlüssel, dass die einzigen zulässigen Eigenschaften Eigenschaften der Sprache L (M) und nicht der Maschine M sind (dennoch ist eine Beschreibung von M die Eingabe für das Problem). Ein Analogon für prägnante Graphprobleme wäre etwa: Eigenschaften, die nur vom Isomorphismustyp des Graphen abhängen.
Joshua Grochow
@ JoshuaGrochow klingt nach einer sehr guten Idee. Es bezieht sich auch auf meine Intuition der Entscheidungsbaumkomplexität (dass Eigenschaften mit linearer Entscheidungsbaumkomplexität schwierig sind) über die Ausweichvermutung, zumindest für monotone Eigenschaften.
Sasho Nikolov