Wie schwer ist es, eine Saite zu mischen?

117

Eine Mischung aus zwei Zeichenfolgen wird gebildet, indem die Zeichen in eine neue Zeichenfolge eingefügt werden, wobei die Zeichen der einzelnen Zeichenfolgen in der angegebenen Reihenfolge bleiben. Zum Beispiel MISSISSIPPIist ein Shuffle von MISIPPund SSISI. Lassen Sie mich einen String als Quadrat bezeichnen, wenn er aus zwei identischen Strings besteht. Zum Beispiel ABCABDCDist quadratisch, weil es sich um ein Shuffle von ABCDund handelt ABCD, aber die Zeichenfolge ABCDDCBAist nicht quadratisch.

Gibt es einen schnellen Algorithmus, um festzustellen, ob eine Zeichenfolge quadratisch ist, oder ist sie NP-hart? Der offensichtliche Ansatz der dynamischen Programmierung scheint nicht zu funktionieren.

Auch werden die folgenden besonderen Fälle schwer sein: (1) Zeichenkette , in denen jedes Zeichen höchstens erscheint vier sechs Mal, und (2) Saiten mit nur zwei unterschiedlichen Charakteren. Wie Per Austrin weiter unten ausführt, kann der Sonderfall, in dem jedes Zeichen höchstens viermal vorkommt, auf 2SAT reduziert werden.


Update: Dieses Problem hat eine andere Formulierung, die einen Härtenachweis erleichtern kann.

Man betrachte einen Graphen G, dessen Eckpunkte die ganzen Zahlen 1 bis n sind. Identifizieren Sie jede Kante mit dem tatsächlichen Abstand zwischen ihren Endpunkten. Wir sagen, dass zwei Kanten von G verschachtelt sind, wenn ein Intervall das andere enthält. Zum Beispiel sind die Kanten (1,5) und (2,3) verschachtelt, aber (1,3) und (5,6) nicht und (1,5) und (2,8) nicht. Eine Übereinstimmung in G ist nicht verschachtelt, wenn kein Kantenpaar verschachtelt ist. Gibt es einen schnellen Algorithmus, um festzustellen, ob G eine nicht verschachtelte perfekte Übereinstimmung aufweist, oder ist das Problem NP-schwer?

  • Das Entmischen eines Strings entspricht dem Auffinden einer nicht verschachtelten perfekten Übereinstimmung in einer disjunkten Cliquen-Union (mit Kanten zwischen gleichen Zeichen). Insbesondere eine unshuffling binär ist entsprechende Zeichenfolge eine nicht verschachtelte perfekte Abstimmung in disjunkter Vereinigung von zu finden zwei Cliquen. Aber ich weiß nicht einmal, ob dieses Problem für allgemeine Grafiken oder für interessante Grafikklassen schwierig ist.

  • Es gibt einen einfachen Polynom-Zeit-Algorithmus, um perfekte Nicht- Kreuzungs- Übereinstimmungen zu finden .


Update (24.06.2013): Das Problem ist behoben! Es gibt nun zwei unabhängige Beweise dafür, dass die Identifizierung quadratischer Zeichenfolgen NP-vollständig ist.

Es gibt auch einen einfacheren Beweis , dass die Suche nach nicht-verschachteltem perfekt passenden NP-schwer ist , aufgrund Shuai Cheng Li und Ming Li im Jahr 2009. Siehe „ Auf zwei offene Problemen von 2-Intervall - Muster “, Theoretische Informatik 410 (24-25 ): 2410–2423, 2009.

Jeffε
quelle
2
Ist die Sequenz nicht nur A000984, die "Anzahl der möglichen Werte einer 2 * n-Bit-Binärzahl, für die die Hälfte der Bits aktiviert und die andere Hälfte deaktiviert ist"?
Travis Brown
5
@ Travis, es sei denn, ich habe ein Missverständnis: Für n = 4 ist 10000111 eine 2 * n-Bit-Binärzahl, für die die Hälfte der Bits aktiviert und die andere Hälfte deaktiviert ist, die jedoch kein Quadrat ist, wie definiert. Da Quadrate nach dieser Logik eine strikte Teilmenge der Menge sind, die A000984 generiert, sollten die Werte für Quadrate über einem binären Alphabet bei gleichen Indizes durch die Sequenz niedriger sein - nein?
Daniel Apon
1
Beobachtung: Unter Verwendung des Graphformalismus sei 2n die Anzahl der Eckpunkte in G. Sei G 'ein Graph, der aus dem Liniendiagramm von G erhalten wird, indem die Kanten zwischen den Eckpunkten addiert werden, die den verschachtelten Kanten von G entsprechen eine unabhängige Menge von Größe n. Es gibt verschiedene Klassen von Graphen, in denen eine maximale unabhängige Menge aus der Polynomzeit berechnet werden kann. Wenn wir diesen Weg gehen, lautet die Frage: Welche schönen Eigenschaften hat G '? (mehr)
Tsuyoshi Ito
2
@ Radu: Ich glaube nicht, dass der Bruchteil von Quadraten zu Nichtquadraten (über Binäralphabeten) zu 1/3 konvergiert. Ich habe einige Monte- Carlo-Simulationen durchgeführt, die auf eine langsame Konvergenz zu 1/2 hindeuten. Daher sind im Grenzfall im Wesentlichen alle binären Zeichenfolgen mit geraden Zahlen von 0 und 1 Quadrate. Dies ist für mich überraschend und kann in einem Algorithmus ausgenutzt werden. Bei größeren Alphabeten scheint der Bruchteil der Quadrate schnell gegen 0 zu konvergieren.
Martin Berger
8
Da diese Frage im heutigen Blog-Beitrag erwähnt wird, wollen wir uns erneut mit der Lösung dieses Problems befassen. Es ist ein Jahr her, seit diese Frage aufgeworfen wurde, und seitdem haben wir viele neue Benutzer gewonnen. Ich habe ein 100-Wiederholungs-Kopfgeld für die Frage ausgesetzt.
Alex ten Brink

Antworten:

66

Michael Soltys und mir ist es gelungen zu beweisen, dass das Problem der Bestimmung, ob eine Zeichenfolge als quadratische Mischung geschrieben werden kann, NP-vollständig ist. Dies gilt auch für ein endliches Alphabet mit nur verschiedenen Symbolen, obwohl unser Beweis für ein Alphabet mit Symbolen geschrieben wurde. Diese Frage ist noch offen für kleinere Alphabete, beispielsweise mit nur Symbolen. Wir haben nicht das Problem , unter der Einschränkung , dass jedes Symbol betrachtet erscheint nur mal (oder, allgemeiner, eine konstante Anzahl von Malen); also diese frage ist noch offen.9 2 67926

Der Beweis verwendet eine Reduktion von Partition. Es ist zu lang, um hier etwas zu posten, aber ein Vorabdruck mit dem Titel "Eine Zeichenfolge entmischen ist -hard" ist auf unseren Webseiten unter folgender Adresse verfügbar:NP3NP

http://www.math.ucsd.edu/~sbuss/ResearchWeb/Shuffle/

und

http://www.cas.mcmaster.ca/~soltys/#Papers .

Der Artikel wurde im Journal of Computer System Sciences veröffentlicht:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Sam Buss
quelle
11
Genial!! (Und zu meiner ungeheuren Erleichterung, ernsthaft nicht trivial.)
Jeffs
15
Vielen Dank. StackExchange war unsere Quelle für diese Frage. Es ist eine großartige Ressource!
Sam Buss
9
@SamBuss eine kleine Bitte: Während Sie Jeffs Frage zitieren, erwähnen Sie nur Per Austrins Lösung im Text. Wenn Sie sich die Antworten ansehen, können Sie auch ein formelles Zitat für die Antworten erstellen (klicken Sie auf die Schaltfläche "Teilen" und klicken Sie auf den Link "Zitieren"). Auf diese Weise können Sie auch ein korrektes Zitat für die Antwort von Per erstellen. Ich erwähne dies nur, damit Personen, die formelle Beiträge auf der Website leisten, auch formelle Anerkennung erhalten. Vielen Dank ! und herzlichen Glückwunsch zum Knacken dieses Problems
Suresh Venkat
2
@SureshVenkat. Danke für den Tipp: das ist nützlich. Ich habe dies der Online-Version des Papiers hinzugefügt.
Sam Buss
Das Problem des Erkennens eines quadratischen Shuffle hat sich jetzt auch für ein binäres Alphabet als schwierig erwiesen: sciencedirect.com/science/article/pii/S0304397519300258
a3nm
58

Für den Sonderfall, den Sie erwähnen, wenn jedes Zeichen höchstens viermal vorkommt, gibt es eine einfache Reduktion auf 2-SAT (es sei denn, ich vermisse etwas ...), wie folgt:

Der entscheidende Punkt ist, dass es für jedes Zeichen (höchstens) zwei gültige Möglichkeiten gibt, die Vorkommen des Zeichens abzugleichen (die dritte Möglichkeit ist das Verschachteln). Verwenden Sie eine boolesche Variable, um darzustellen, welche der beiden Übereinstimmungen ausgewählt wurde. Nun ergibt eine Zuweisung zu diesen Variablen ein gültiges Auflösen der Zeichenfolge, wenn für jedes Kantenpaar, das verschachtelt ist, nicht beide ausgewählt wurden. Diese Bedingung kann durch eine Disjunktion der Variablen (möglicherweise negiert) entsprechend den zwei beteiligten Zeichen genau beschrieben werden.

Per Austrin
quelle
Nett. Dieselbe Idee lässt sich auf Zeichenfolgen verallgemeinern, bei denen jedes Zeichen höchstens sechsmal vorkommt, das Ergebnis jedoch eine Instanz von 5-SAT ist. :-(
Jeffs
2
Diese Antwort ist der Favorit, um das Kopfgeld zu gewinnen.
Jeffs
Das scheint zu beweisen, dass es sich bei dem NPC um ein Problem handelt und warum wir lange Konferenz- und Tagebuchnachweise benötigen.
T ....
@Turbo Viel verspätet, aber dies beweist nicht, dass das Problem ein NPC ist, da 2-SAT kein NPC ist. Es ist in P.
Steven Stadnicki
Funktioniert diese Reduzierung auf 2-SAT, wenn die Alphabetgröße nicht begrenzt ist?
Mohammad Al-Turkistany
11

Hier ist ein Algorithmus, der eine gewisse Chance hat, korrekt zu sein, obwohl es schwierig zu beweisen scheint, und ich würde das Haus nicht darauf wetten ...

GeGee

GGGG

>1

Nach der gierigen Auswahl löschen wir den Graphen erneut und so weiter. Der Prozess endet, wenn der Graphen (hoffentlich) eine perfekte Übereinstimmung ohne Verschachtelung darstellt.

Zuerst dachte ich, das wäre ungefähr so, als hätte man einen kleinen Ausblick auf den gierigen Algorithmus und würde nicht wirklich funktionieren, aber ich fand es überraschend schwierig, ein Gegenbeispiel zu finden.

Per Austrin
quelle
Ich bin skeptisch gegenüber der zweiten gierigen Phase, aber das Löschen des Graphen scheint nützlich zu sein. Können Sie im ursprünglichen String-Kontext, in dem der Graph die disjunkte Vereinigung von Cliquen ist, etwas über die Struktur des gelöschten Graphen sagen? Ist es immer noch eine disjunkte Vereinigung von Cliquen? (Mit anderen Worten, können Sie die Vorkommen der einzelnen Zeichen in der Eingabezeichenfolge so partitionieren, dass Zeichen in verschiedenen Teilen nicht übereinstimmen können?)
Jeffε
2
Betrachten Sie für die zweite Frage die Zeichenfolge 'aaaa'. Durch das Löschen werden die Kanten 1-4 und 2-3 entfernt, was einen 4-Zyklus ergibt. Zwei Variationen des zweiten gierigen Schritts, die ebenfalls ausreichen würden und zu denen ich keine Gegenbeispiele finden konnte, sind: 1) Ein gelöschter Graph hat eine nicht verschachtelte perfekte Übereinstimmung, wenn er eine perfekte Übereinstimmung hat (dies scheint mit dem gierigen Schritt unvergleichbar zu sein). . 2) In einem gespülten Graph mit einer nicht-Verschachtelung perfekten Abstimmung, jeder wird in Kante verwendet einige nicht-Verschachtelung perfekte Abstimmung (das stärker ist als sowohl den gierige Schritt und das erste Element so sollte es einfacher sein , zu widerlegen).
Per Austrin
11

Die von Sam Buss und mir im November 2012 vorgeschlagene Lösung (die zeigt, dass ein Quadrat in NP-hard durch Reduzierung von 3-Partition entmischt wird) ist jetzt ein im Journal of Computer System Sciences veröffentlichter Artikel:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

Michael Soltys
quelle
2
Dies sollte eigentlich eine Änderung von Sam Buss 'früherer Antwort sein und keine separate Antwort. Sie können auf "Bearbeiten" klicken, um einer anderen Person eine Bearbeitung vorzuschlagen. Ihre Bearbeitung wird dann von anderen Benutzern der Website überprüft.
DW
11

Romeo Rizzi und Stéphane Vialette beweisen, dass das Erkennen von quadratischen Zeichenfolgen in ihrem 2013 erschienenen Aufsatz " Über das Erkennen von Wörtern, die Quadrate für das Zufallsprodukt sind " NP-vollständig ist , indem sie das längste binäre Teilfolgeproblem reduzieren. Sie geben an, dass die Komplexität des Unmischens einer binären Zeichenfolge noch offen ist.

Ein noch einfacherer Beweis dafür, dass das Finden einer nicht verschachtelten perfekten Übereinstimmung NP-vollständig ist, wird von Shuai Cheng Li und Ming Li in ihrer Arbeit von 2009 " Über zwei offene Probleme von 2-Intervall-Mustern " gegeben. Sie verwenden jedoch eine von der Bioinformatik übernommene Terminologie. Anstelle von "Perfect Non-Nested Matching" nennen sie es das "DIS-2-IP- -Problem". Die Äquivalenz zwischen den beiden Problemen wird von Blin, Fertin und Vialette beschrieben :{<,}

Das 2-IP-DIS- -Problem hat eine unmittelbare Formulierung in Bezug auf eingeschränkte Übereinstimmungen in allgemeinen Graphen: Gegeben ist ein Graph zusammen mit einer linearen Ordnung der Eckpunkte von , der 2-IP -DIS- ist äquivalent zum Finden einer maximalen Kardinalität, die in mit der Eigenschaft übereinstimmt , die für zwei beliebige unterschiedliche Kanten und von gilt weder und nor{<,}GπG{<,}MG{u,v}{u,v}Mmin{π(u),π(v)}<min{π(u),π(v)}max{π(u),π(v)<max{π(u),π(v)}min{π(u),π(v)}<min{π(u),π(v)} und auftreten.max{π(u),π(v)}<max{π(u),π(v)}

Update (25. Februar 2019): Bulteau und Vialette haben gezeigt, dass das Entscheidungsproblem beim Entmischen einer binären Zeichenfolge in ihrem Artikel NP-vollständig ist. Das Erkennen von binären Mischquadraten ist NP-schwer .

Mohammad Al-Turkistany
quelle
Ich sehe den Zusammenhang nicht, und ich sehe nicht, wo die Autoren behaupten, dass das Auflösen eines Strings ihrem Problem entspricht.
Suresh Venkat
2
Sie sagen nicht, dass es dem Entmischen entspricht; Es ist ein allgemeineres Problem.
Jeffs
@SureshVenkat Ich habe meine Antwort bearbeitet, ich hoffe es ist klarer. Grundsätzlich heißt es in der Fußnote, dass zwei beliebige Kanten im Matching ( ) nicht verschachtelt sind. M
Mohammad Al-Turkistany
In der tatsächlich veröffentlichten Version ist die Äquivalenz auf Seite 320 angegeben. Books.google.com/…
Mohammad Al-Turkistany,
Bearbeitet, um das Lede zu beerdigen .
Jeffs
9

Hilft das?

http://users.soe.ucsc.edu/~manfred/pubs/J1.pdf

Aaron Sterling
quelle
7
Schöne Referenz. Es ist schwer zu erkennen, wie sich die Ergebnisse auf mein Problem auswirken würden, aber vielleicht würden die Techniken helfen. Es ist leicht zu erkennen, ob eine gegebene Zeichenfolge X ein Shuffle von zwei Kopien einer anderen gegebenen Zeichenfolge Y ist. Das beigefügte Papier beweist, dass es schwer zu entscheiden ist, ob eine gegebene Zeichenfolge X ein Shuffle einer beliebigen Anzahl von Kopien einer anderen gegebenen Zeichenfolge Y ist. Ich möchte wissen, ob eine bestimmte Zeichenfolge X eine Mischung aus zwei Kopien der UNBEKANNTEN Zeichenfolge Y ist.
Jeffs
5

NIEMALS VERSTÄNDNIS, DIESE ANTWORT IST FALSCH. Bei Eingabe von "AABAAB" schlägt dies fehl: Wenn die ersten beiden A gierig miteinander verglichen werden, ist es unmöglich, die verbleibenden Symbole zuzuordnen. Ich lasse es lieber liegen, als es zu löschen, damit andere nicht den gleichen Fehler machen.

Es scheint mir immer sicher zu sein, jedes nachfolgende Zeichen des vermeintlichen Quadrats gierig einem anderen gleichen Zeichen zuzuordnen, das sich in einer möglichst frühen Position befindet. Das heißt, ich denke, der folgende lineare Zeitalgorithmus sollte funktionieren:

Durchlaufen Sie jede Position i in der Eingabezeichenfolge, i = 0, 1, 2, ... n. Überprüfen Sie für jede Position i, ob diese Position bereits mit einer früheren Position in der Zeichenfolge abgeglichen wurde. Wenn nicht, vergleichen Sie es mit einem gleichen Zeichen, das nach der letzten bereits übereinstimmenden Position kommt und ansonsten so früh wie möglich in der Zeichenfolge ist. Wenn für ein Zeichen keine Übereinstimmung gefunden wird, deklarieren Sie, dass die Eingabe kein Quadrat ist. Andernfalls handelt es sich um den Zeichensatz im ersten Paar jeder Übereinstimmung.

Hier ist es in Python:

def sqrt (S):
    Übereinstimmungen = []
    i, j = 0, 0
    während ich <len (S):
        wenn j <len (entspricht) und entspricht [j] [1] == i:
            i + = 1
            j + = 1
            fortsetzen
        wenn Übereinstimmungen:
            k = stimmt mit [-1] [1] + 1 überein
        sonst:
            k = 1
        während k <len (S) und S [k]! = S [i]:
            k + = 1
        wenn k> = len (S):
            Ausnahme auslösen ("Kein Quadrat")
        match.append ((i, k))
        i + = 1
    return "" .join (S [a] für a, b in Übereinstimmungen)

print sqrt ("ABCABDCD")

Hier ist i die Hauptschleifenvariable (die Position, mit der wir übereinstimmen wollen), j ist ein Zeiger auf das Array von übereinstimmenden Paaren, der die Überprüfung beschleunigt, ob die Position i bereits übereinstimmt, und k ist ein Index, der zum Suchen verwendet wird das Zeichen, das mit dem Zeichen an Position i übereinstimmt. Es ist eine lineare Zeit, da i, j und k durch die Zeichenfolge monoton ansteigen und jede Iteration der inneren Schleife eine von ihnen erhöht.

David Eppstein
quelle
4
War dort. Habe das gemacht. :-)
Jeffs
5

Update: Es ist nicht sinnvoll, über die Schwierigkeit zu sprechen, eine perfekte Übereinstimmung zu finden, die nicht verschachtelt und nicht gekreuzt ist, wenn die Bezeichnungen von 1 bis n reichen, da es nur eine solche gibt. (Ja, ich mache mir selbst einen Kick.) Es wäre jedoch sinnvoll, wenn man einen größeren Bereich auf den Etiketten ansieht ... also sehe ich immer noch Hoffnung, aber es könnte doch ziemlich sinnlos sein. Ich würde das sicherlich noch weiter verfolgen müssen.


Ich kann mir vorstellen, warum es schwierig sein könnte, ein Matching zu finden, das nicht verschachtelt und nicht kreuzt. Lassen Sie mich ein solches Matching als disjunktes Matching bezeichnen . Ich bin mir nicht sicher, inwieweit dies hilft, aber ich möchte die Argumentation trotzdem vorstellen. (Ich möchte darauf hinweisen, dass meine Argumentation in der jetzigen Form nicht vollständig ist und das Detail, das ich auslasse, möglicherweise von entscheidender Bedeutung ist. Ich stelle mir jedoch vor, dass dies ein Anfang sein könnte.)

Ich werde mit einem etwas anderen Problem beginnen. Gibt es bei einem Graphen dessen Kanten mit Farben gefärbt sind und dessen Eckpunkte mit bis , eine disjunkte Übereinstimmung, die genau eine Kante jeder Farbe enthält? Dieses Problem scheint NP-schwer zu sein (das Argument dafür ist sowohl vollständig als auch unkompliziert - es sei denn, mir fehlt etwas). Die Reduktion spuckt einen Graphen aus, der eine disjunkte Vereinigung von Cliquen darstellt.k 1 nGk1n

Die Reduktion beruht auf Disjoint Factors , einem NP-vollständigen Problem, das in [1] eingeführt wurde. Eine Instanz von disjunkten Faktoren wird durch eine Zeichenfolge über einem Alphabet der Größe , und die Frage ist, ob es disjunkte Faktoren gibt, wobei ein Faktor eine Teilzeichenfolge ist, die mit demselben Buchstaben beginnt und endet. und zwei Faktoren sind unzusammenhängend, wenn sie sich in der Zeichenfolge nicht überlappen (beachten Sie, dass insbesondere das Verschachteln ebenfalls nicht zulässig ist).kkk

Lassen Sie mich mit die Elemente des großen Alphabets bezeichnen, die der Disjoint Factors-Instanz zugeordnet sind.a1,,akk

Erstellen Sie bei einer Instanz von disjunkten Faktoren, dh einer Zeichenfolge mit der Länge , ein Diagramm mit Scheitelpunkten mit Scheitelpunktbezeichnungen von bis . Fügen Sie eine Kante zwischen den Eckpunkten und wenn die entsprechenden Positionen den gleichen Buchstaben haben (sagen Sie ), und färben Sie die Kante mit Farbe .nn1nuvai(u,v)i

Der Nachweis der Reduktion ergibt sich im Wesentlichen aus den Definitionen. Bei disjunkten Faktoren haben wir eindeutig ein disjunktes farbiges Matching, wählen Sie lediglich die durch die disjunkten Faktoren gegebenen Kanten aus, und es ist leicht zu erkennen, dass das resultierende Matching sowohl bunt als auch disjunkt ist. Wenn es umgekehrt eine disjunkte farbige Übereinstimmung gibt, haben wir k disjunkte Faktoren, einen für jeden Buchstaben, weil die Übereinstimmung bunt ist (und daher einen Faktor pro Buchstabe auswählt) und disjunkt ist (so dass sich die entsprechenden Faktoren nicht überlappen würden) ).kkk

Nehmen Sie die folgenden Änderungen an der so erstellten Grafik vor , um die Farben zu entfernen und die Übereinstimmung zu perfektionieren, wenn auch in einem möglicherweise größeren Bereich :

Es sei die Teilmenge von Eckpunkten mit Bezeichnungen, die Positionen sind, die dem Buchstaben . Wenn hat Eckpunkte, fügen Sie dann neue Eckpunkte und induziert ein komplettes zweiteiliges Graphen zwischen und den neu hinzugekommenen Ecken. Wiederholen Sie dies natürlich für jeden Buchstaben.UaaUaA(A2)Ua

Grob gesagt müssen die neu eingeführten Scheitelpunkte mit den Scheitelpunkten von abgeglichen werden, wenn der Graph eine perfekte Übereinstimmung hervorrufen soll. Mit eines Scheitelpunktpaars werden alle Scheitelpunkte gesättigt, und die Kante zwischen den verbleibenden Scheitelpunkten entspricht dem Disjunktionsfaktor . Ich habe die Zahlen, die man mit den neu hinzugefügten Eckpunkten verknüpfen muss, nicht ausgearbeitet ... beachte, dass sie so sein müssen, dass die resultierende Übereinstimmung disjunkt ist. Ich habe nur das Gefühl (lese: hoffe), dass es getan werden kann!Ua

[1] Zu Problemen ohne Polynomkerne : Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows und Danny Hermelin, J. Comput. Syst. Sci.

Neeldhara
quelle
3
Ich bin verwirrt. Ist (1,2), (3,4), (5,6), ..., (n-1, n) nicht die EINZIGE perfekte disjunkte Übereinstimmung?
Jeffs
Sobald ich zum Szenario der perfekten Übereinstimmung übergehe, ändere ich die Konstruktion und füge viele neue Scheitelpunkte hinzu (beachte, dass ich für jedes a im Alphabet | U_a | -2 neue Scheitelpunkte hinzufüge). Daher wird n entsprechend explodieren - ungefähr auf 2n-2k für ein k-großes Alphabet. Ich hoffe, dass ich klargestellt habe, dass die Reduzierung unvollständig ist, da ich nicht angegeben habe, welche Nummern den neuen Scheitelpunkten zugewiesen sind, aber ich hoffe, dass sie ohne allzu große Schwierigkeiten erweitert werden können. Allerdings muss ich mir einige Gedanken machen, bevor ich mehr sagen kann.
Neeldhara
1
Ich denke, dass JeffEs Kommentar den Sinn hat, dass es einfach ist, eine perfekte Übereinstimmung zu finden, die nicht verschachtelt und nicht gekreuzt ist (oder deren Abwesenheit zu melden), da es nur eine Möglichkeit gibt.
Tsuyoshi Ito
2
Ich spreche nicht über den Inhalt Ihrer Beweisidee, aber ich spreche über den ersten Satz Ihrer Antwort: "Ich kann mir vorstellen, warum es schwierig sein könnte, eine perfekte Übereinstimmung zu finden, die nicht verschachtelt und nicht kreuzt." Diese Aufgabe ist aus dem Grund, den JeffE schrieb, einfach.
Tsuyoshi Ito
2
Ohne die durch das Problem des disjunkten Faktors auferlegte Farbeinschränkung (höchstens eine Kante jeder Farbe) ist es auch einfach, maximale disjunkte Übereinstimmungen zu finden.
Jeffs
1

Der Ansatz funktioniert nicht: Das Zerlegen eines gemischten Quadrats durch Herausnehmen zweier übereinstimmender Buchstaben führt nicht zu gemischten Quadraten ... Siehe Radus Kommentare unten.


Ein Vorschlag mit Bereich Verkettungs Grammatiken (RCG siehe http://hal.inria.fr/inria-00073347/en/ ): Ich bin‘ habe den Eindruck, dass die folgende einfache RCG Ihre Sprache über einen endlichen‚Quadrate gemischt‘erkennt Alphabet , BEARBEITET nach Radus erstem Kommentar: wobei Bereich über und das bezeichnet Zeichenfolge.Σ

S(XY)A(X,Y)(1)A(aX1,aX2Y1Y2)A(X1,Y1)A(X2,Y2)(2)A(ε,ε)ε(3)
aΣε

Die Grammatik prüft mit dem zweiten Prädikat, ob ein Buchstabe des ersten Wortvorkommens mit dem gleichen Buchstaben des zweiten Wortvorkommens übereinstimmt. Dann wird erraten, wie der Rest der verbleibenden ersten , dh mit einem Teil des Restes, nämlich , . Alles vor gehört daher zur ersten ; Wir nennen es und wir vermuten, dass es mit einem Suffix ab . Beachten Sie, dass und möglicherweise Buchstaben aus beiden Instanzen des Wortes enthalten, und nur Buchstaben aus der ersten Instanz.X1Y1Y1X2Y2Y1Y2X1X2

Zum Beispiel ist hier eine mögliche Ableitung Ihres Strings : abcabdcd

S(abcabdcd)A(abc,abdcd)(by 1,X=abc,Y=abdcd)A(bc,bdcd)A(ε,ε)(by 2,X1=bc,Y1=bdcd,X2=Y2=ε)A(c,c)A(d,d)A(ε,ε)(by 2)A(ε,ε)A(ε,ε)A(d,d)A(ε,ε)(by 2)A(ε,ε)A(d,d)A(ε,ε)(by 3)A(d,d)A(ε,ε)(by 3)A(ε,ε)A(ε,ε)A(ε,ε)(by 2)3εi.e. success

Für ist 0011

S(0011)A(0,011)A(ε,ε)A(1,1)A(1,1)ε

Nun zeigen Boullier in dem zuvor verknüpften Papier , dass es ein dynamisches Programmierung Polynomialzeitalgorithmus für RCG, das Ihre Frage beantwortet , ob die obige Grammatik ist richtig war. Die Idee ist, dass, obwohl ich oben die Instanzen der Variablen , usw. als Zeichenfolgen dargestellt habe, es sich tatsächlich um Intervalle innerhalb der Eingabezeichenfolge handelt, die ordnungsgemäß tabelliert werden können.XY

Sylvain
quelle
Gibt es eine Ableitung, die S (0011) nach bringt ? (Es sollte eine geben.)ϵ
Radu GRIGore
Ich glaube nicht.
Serge Gaspers
Auch A (10,011010) -> A (0,101) A (0,0) -> , aber ich glaube, 10011010 ist kein Quadrat. ϵ
Radu GRIGore
Danke für die Rücksendung; Ich habe die Grammatik ein wenig geändert und habe sogar eine kleine Intuition, wie es funktionieren könnte.
Sylvain
3
Bitte. Hier ist mehr für die aktualisierte Grammatik :) A (00,000110) -> A (0,011) A (0,0) -> , aber 00000110 ist kein Quadrat. Es scheint auch keine Ableitung für 100110101010 zu geben, bei der es sich um ein Quadrat handelt. ϵ
Radu GRIGore
1

Update: Wie Tsuyoshi Ito in den Kommentaren ausführt, hat dieser Algorithmus eine exponentielle Laufzeit.

Ursprünglicher Beitrag:

Hier ist, wie ich das in der realen Welt programmieren würde.

Wir erhalten eine Zeichenkette S = (S [1], ..., S [n]). Für jedes Präfix S_r = (S [1], ..., S [r]) gibt es eine Menge {(T_i, U_i)} von Zeichenfolgenpaaren, so dass S_r eine Mischung von (T_i, U_i) ist. und T_i ist ein Präfix von U_i (dh U_i 'beginnt mit' T_i '). S_r selbst ist genau dann ein Quadrat, wenn diese Menge ein Paar (T_i, U_i) mit T_i = U_i enthält.

Nun müssen wir nicht alle diese Paare erzeugen; wir müssen nur das Suffix V_i jeder Zeichenkette U_i erzeugen, die durch Entfernen ihrer Kopie von T_i erhalten wird. Dadurch wird eine (möglicherweise exponentielle) Anzahl irrelevanter Duplikate beseitigt. Jetzt ist S_r genau dann ein Quadrat, wenn diese Gruppe von Suffixen die leere Zeichenfolge enthält. So wird der Algorithmus:

Initialise: SuffixSet = {<empty string>} ; r = 0
Loop: while (r < n) {
  r = r + 1
  NextSuffixSet = {}
  for each V in SuffixSet {
    if (V[1] == S[r]) Add V[2...] to NextSuffixSet // Remove first character of V
    Add V||S[r] to NextSuffixSet // Append character S[r] to V
    }
  SuffixSet = NextSuffixSet
  }
Now S is a square if and only if SuffixSet contains the empty string.

Zum Beispiel, wenn S AABAAB ist:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB, AABA}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA, AABAA}
r=6: S[r] = B; SuffixSet = {AA, BAAB, <empty string>, BB, ABAB, AABAAB}

Wir können alle Suffixe verwerfen, die länger als die Hälfte der Eingabezeichenfolge sind. Dies vereinfacht Folgendes:

r=0: SuffixSet = {<empty string>}
r=1: S[r] = A; SuffixSet = {A}
r=2: S[r] = A; SuffixSet = {<empty string>, AA}
r=3: S[r] = B; SuffixSet = {B, AAB}
r=4: S[r] = A; SuffixSet = {BA, AB}
r=5: S[r] = A; SuffixSet = {BAA, B, ABA}
r=6: S[r] = B; SuffixSet = {AA, <empty string>, BB}

Ich habe dies in C ++ programmiert und es funktioniert an allen hier angegebenen Beispielen. Ich kann den Code posten, wenn jemand daran interessiert ist. Die Frage ist: Kann die Größe von SuffixSet schneller als polynomial wachsen?

TonyK
quelle
3
Ich habe es auch versucht, aber Experimente zeigen, dass die Größe von SuffixSet in n exponentiell zu wachsen scheint, wenn die ursprüngliche Zeichenfolge (AB) ^ n ist.
Tsuyoshi Ito
1

EDIT: Dies ist eine falsche Antwort.


Sylvain schlug ein RCG vor, das für diese "Shuffle Squares" leider nicht geeignet war. Ich denke jedoch, dass es einen gibt (EDIT: kein RCG, siehe Kurts Kommentare unten!) , Der wie folgt aussieht:

S(Y)A(ϵ,Y)(1)A(X,ZY)A(XZ,Y)(2)A(aX,aY)A(X,Y) for every aΣ(3)A(ϵ,ϵ)ϵ(4)

aabbabab(1,2)(3)(2)und sehen, ob es eine Übereinstimmung an einer späteren Position gibt. Wichtig ist, dass dies nur in eine Richtung erlaubt ist!

Hier ist eine Ableitung für (ein Gegenbeispiel zu RCG):100110101010

S(100110101010)A(ϵ,100110101010)(1)A(1001,10101010)(2)A(01,101010)(3)A(011,01010)(2)A(1,010)(3)A(10,10)(2)A(ϵ,ϵ)(3)ϵ(4)

Ich habe keinen formalen Beweis dafür erarbeitet, dass diese Grammatik tatsächlich genau die "Zufallsquadrate" erfasst, aber es sollte nicht zu schwer sein. Sylvain erwähnte bereits, dass das Entscheidungsproblem für RCGs polynomisch ist.

DaniCL
quelle
Ich verstehe nicht, wie dies möglicherweise in der Polynomzeit implementiert werden könnte: Wenn Sie mit 000102030 beginnen, können Sie für x erreichen , das einer der folgenden Zeichenfolgen entspricht: 123, 01230, 01203, 0012030, 01023, 0010230, 0010203, 000102030. (Ja, ich habe mir das von Sylvain verlinkte Dokument angesehen, aber es sieht für mich ganz französisch aus.)2 3A(x,ϵ)23
Radu GRIGore
5
@DaniCL, Zum zweiten Gedanken ... Müssen die Parameter in der RHS der Produktionsregeln zusammenhängende Bereiche der Eingabe sein? Ich habe das nicht explizit in der Definition des Boullier-Papiers gesehen, aber es scheint so zu sein, wie es verwendet wird. In der Analyse der Laufzeit des Parsing-Algorithmus heißt es, dass die Anzahl der möglichen Argumente für die Klauseln O (n ^ 2h) ist, wobei h die maximale Länge der Klauseln und n die Eingabelänge ist. In Ihrer Grammatik ist XZ im Allgemeinen in der ursprünglichen Eingabe nicht zusammenhängend.
Kurt
3
@ Kurt, ich glaube du hast den Fehler gefunden. In einem anderen Artikel ("Chinesische Zahlen, MIX-, Scrambling- und Range Concatenation-Grammatiken") stellt Boullier explizit fest: "Natürlich können nur aufeinanderfolgende Bereiche zu neuen Bereichen verkettet werden. In PRCG werden Terminals, Variablen und Argumente in einer Klausel soll durch einen Substitutionsmechanismus an Bereiche gebunden sein. " Dies bedeutet wahrscheinlich, dass meine Grammatik keine gültige RCG ist, dass Radus Zweifel vernünftig waren und dass dieser Ansatz auch nicht funktioniert.
DaniCL
2
@ Kurt ist richtig. Ohne die Einschränkung der Kontiguität bin ich mir ziemlich sicher, dass ich einen Satz von Produktionsregeln erstellen kann, die die NP-vollständige Sprache UNARY 3PARTITION erkennen. Jeder Satz nicht negativer Ganzzahlen kann durch eine Zeichenfolge in der Sprache (1 * 0) ^ * unär codiert werden. UNARY 3PARTITION ist die Menge aller solcher Zeichenfolgen, deren codierte Menge in Teilmengen mit drei Elementen aufgeteilt werden kann, die alle dieselbe Summe aufweisen. (Siehe en.wikipedia.org/wiki/3-partition_problem .)
Jeffs
1
Grammatik für UNARY 3PARTITION: S (X0Y0Z) -> A (e, X0, Y0, Z); A (W, 1X, Y, Z), A (W, X, 1Y, Z), A (W, X, Y, 1Z) -> A (W1, X, Y, Z); A (W, 0X, 0Y, 0Z) -> B (W, XYZ); B (W, e) -> e; B (W, XOYOZ) -> C (W, W, XO, YO, Z); C (W, 1 V, 1 X, Y, Z), C (W, 1 V, X, 1 Y, Z), C (W, 1 V, X, Y, 1 Z) -> C (W, V, X, Y, Z); C (W, E, X, Y, Z) -> B (W, XYZ)
Radu GRIGore