Positive topologische Reihenfolge, nimm 2

12

Dies ist eine Fortsetzung von David Eppsteins jüngster Frage und wird durch dieselben Probleme motiviert.

Angenommen, ich habe einen Tag mit reellen Zahlengewichten auf seinen Scheitelpunkten. Anfangs sind alle Scheitelpunkte nicht markiert. Ich kann die Menge der markierten Scheitelpunkte ändern, indem ich entweder (1) einen Scheitelpunkt ohne nicht markierte Vorgänger markiere oder (2) einen Scheitelpunkt ohne markierte Nachfolger deaktiviere. (Daher ist die Menge der markierten Scheitelpunkte immer ein Präfix der Teilreihenfolge.) Ich möchte eine Folge von Markierungs- / Deaktivierungsoperationen finden, die mit allen markierten Scheitelpunkten endet, sodass das Gesamtgewicht der markierten Scheitelpunkte immer nicht negativ ist .

  • Wie schwer ist es, eine solche Abfolge von Operationen zu finden? Im Gegensatz zu Davids Problem ist nicht einmal klar, dass es sich um ein NP-Problem handelt. Im Prinzip (obwohl ich keine Beispiele habe) könnte jede legale Zugsequenz eine exponentielle Länge haben. Das Beste, was ich beweisen kann, ist, dass das Problem in PSPACE liegt.

  • Ist das Aufheben der Markierung tatsächlich nicht erforderlich? Wenn es eine gültige Bewegungssequenz gibt, muss es eine gültige Bewegungssequenz geben, die niemals einen Scheitelpunkt aufhebt? Eine bejahende Antwort würde dieses Problem macht identisch zu Davids . Andererseits, wenn das Entfernen von Markierungen manchmal notwendig ist, sollte es ein kleines Beispiel (mit konstanter Größe) geben, das dies beweist.

Jeffε
quelle
1
Dieses Papier zeigt, dass ein lose verwandtes Problem PSPACE-schwer ist: arxiv.org/abs/1009.3217
Jeffs
Klingt sehr nach einem Kieselspiel: en.wikipedia.org/wiki/Pebble_game .
Warren Schudy
Ein aktuelles Pebbling-Paper: cs.utoronto.ca/~philipp/pages/papers/BWPebbling.pdf . Das Spiel mit schwarzen Steinen ähnelt Ihrem, unterscheidet sich jedoch darin, dass Zwischenknoten auch dann nicht markiert werden können, wenn ein Nachfolger markiert ist.
Warren Schudy

Antworten:

5

In unserem regulären 666-Forschungsseminar haben wir den folgenden Beweis erbracht.

Wir beginnen mit einigen Definitionen. Sei P unser Poset. Nehmen wir der Einfachheit halber an, dass keines der Gewichtungen die Summe Null ergibt. Bezeichne das Gewicht eines Eckpunktes mit w (x) und die Summe der Gewichte einer Menge mit w (X). Wir sagen, dass eine Menge X Y-up (geschlossen) ist, wenn sie in Y enthalten ist und jedes Element von Y, das größer als ein Element von X ist, auch in X. Ebenso sagen wir, dass eine Menge X Y-down ist, wenn es ist ist in Y enthalten und jedes Element von Y, das kleiner als ein Element von X ist, ist auch in X. In dieser Sprache muss die Menge der markierten Elemente immer P-down sein.

Wir beweisen durch Widerspruch. Nehmen Sie die kürzeste Markierungs- / Deaktivierungssequenz, die jedes Element markiert. Wir nennen solche Sequenzen voll. Berücksichtigen Sie zu jedem Zeitpunkt die zuvor markierten Elemente, die jetzt nicht mehr markiert sind. Kennzeichnen Sie diesen Satz durch U.

Behauptung: w (U)> 0.

Beweis: Wir beweisen, dass das Gewicht jedes U-Up-Sets, X, positiv ist. Der Beweis erfolgt durch Induktion über die Größe von X. Wenn es eine X-Down-Menge Y gibt, so dass w (Y)> 0 ist, dann wissen wir durch Induktion, dass w (X \ Y)> 0 ist (da dies der Fall ist) X-up) haben wir auch w (X)> 0. Wenn für jede X-down-Menge, Y, wir w (Y) <0 haben, dann erhalten wir eine kürzere vollständige Sequenz, indem wir bis zu diesem Punkt alle Markierungen und Unmarkierungen der Elemente von X aus unserer Sequenz löschen. Wir sind mit dem Nachweis des Anspruchs fertig.

Angenommen, wir haben eine vollständige Sequenz, in der w (U)> 0 für die Menge U der derzeit nicht markierten Elemente ist. Nehmen Sie die Reihenfolge, die wir daraus erhalten, indem Sie die erste Markierung für jedes Element vornehmen und niemals die Markierung aufheben. Es ist klar, dass dies auch eine vollständige Sequenz ist, die befriedigt, dass die Menge der markierten Elemente immer P-down ist. Darüber hinaus ist die Summe der Gewichte immer mindestens so hoch wie in der ursprünglichen Sequenz, da zu einem bestimmten Zeitpunkt die Differenz w (U) ist. Wir sind fertig.

Mit dieser Methode kann man sogar beweisen, dass statt der Markierung von P als Ganzes nur eine Teilmenge von P markiert werden soll. Dies kann mit einer Folge von Markierungen gefolgt von einer Folge von Aufhebungen erfolgen. Der Beweis ist derselbe, mit der Ausnahme, dass am Ende einige Elemente, U, nicht markiert bleiben, diese jedoch an das Ende der Sequenz verschoben werden können, da das Gewicht eines U-up-Sets positiv ist.

domotorp
quelle
1
Ihre Definitionen von Y-up und Y-down sind identisch. Vermutlich eine Teilmenge von X Y ist Y-down , wenn jedes Element von Y , das ist kleiner als ein Element von X ist auch in X.
Jeffε
1
Sehr cool! Die Antwort könnte klarer sein, wenn in der ersten Zeile angegeben ist, welche Aussage Sie beweisen. Ich nehme an, es ist ein Beweis dafür, dass das Aufheben der Markierung niemals erforderlich ist (wenn Sie es mit dem Aufheben der Markierung lösen können, können Sie eine Sequenz finden, die es auch löst, ohne jemals etwas aufzuheben). (Und nicht zB ein Beweis, dass dieses Problem NP-hart / PSPACE-hart ist, oder ein Polynom-Zeit-Algorithmus, der entscheiden kann, ob eine solche Markierungssequenz existiert (oder sie findet).) Auch später in der Beschreibung, wo es heißt "an jedem Punkt", ich weiß nicht, ob dies "an allen Punkten" oder "an irgendeinem Punkt" bedeutet; Ich vermute, Sie meinen das erstere?
DW