Reicht es aus, für ein Sortiernetzwerk polynomiell viele 0-1-Sequenzen zu sortieren?

Das 0-1-Prinzip besagt, dass, wenn ein Sortiernetzwerk für alle 0-1-Sequenzen funktioniert, es für einen beliebigen Satz von Zahlen funktioniert. Gibt es ein so dass, wenn ein Netzwerk jede 0-1-Sequenz von S sortiert, es jede 0-1-Sequenz sortiert und die Größe von in polynomial ist ? $S\subset \{0,1\}^n$ $S$ $n$

Wenn beispielsweise aus allen Sequenzen besteht, in denen höchstens Läufe (Intervalle) von Einsen vorhanden sind, gibt es ein Sortiernetzwerk N und eine Sequenz, die nicht nach N geordnet ist, wenn alle Mitglieder von nach N geordnet sind? $S$ $2$ $S$

Antwort: Wie aus der Antwort und den Kommentaren zu sehen ist, gibt es für jede unsortierte Zeichenfolge ein Sortiernetzwerk, das jede andere Zeichenfolge sortiert. Ein einfacher Beweis dafür ist der folgende. Sei der String so, dass für immer und . Da unsortiert ist, sollte nach dem Sortieren . Vergleiche mit jedem für das $s=s_1\ldots s_n$ $s_i=0$ $i<k$ $s_k=1$ $s$ $s_k$ $0$ $k$ $i$ . Dann vergleiche jedes Paar so, dass und oft sind. Dies lässt die ganze Zeichenfolge sortiert, außer vielleicht für , die für unsortiert ist , und für bestimmte andere Zeichenfolgendie mehr ‚s als . Vergleichen Sie nun für downto Ausnahme der Stelle, an der in . Dies wird alles außer sortieren. $s_i=1$ $(i,j)$ $i\ne k$ $j\ne k$ $s_k$ $s$ $1$ $s$ $s_k$ $i=n$ $1$ $s_k$ $s$ $s$

Update: Ich frage mich, was passiert, wenn wir die Tiefe des Netzwerks auf . $O(\log n)$

ds.algorithms sorting sorting-network domotorp
quelle

Es scheint möglich zu sein, dass Sie die Größe des Sortiernetzwerks so einschränken müssen, dass sie kleiner als die Größe von

. Könnte das Netzwerk sonst nicht einfach überprüfen, ob die Eingabe eines der Elemente von

und richtig handeln, wenn ja, sonst falsch handeln?

S

$S$

S

$S$

usul

@usul: Ich glaube nicht, dass ein Sortiernetzwerk so etwas überprüfen kann. Wie auch immer, es ist nur natürlich, mit Sortiernetzen zu arbeiten, deren Größe in

polynomial ist .

n

$n$

Domotorp

Antworten:

Es scheint nicht. Ian Parberry nimmt Bezug auf einen Artikel von Chung und Ravikumar, wo sie angeblich eine rekursive Konstruktion eines Sortiernetz geben , die jeden bitstring aber ein, und weiter ableiten , dass das Problem der Überprüfung eines Sortiernetz ist sortiert - abgeschlossen. Ich kann das Originalpapier nicht sofort finden, aber es entspricht mit Sicherheit (meiner) Intuition. $co$ $NP$

Bearbeiten zum Hinzufügen: Es ist tatsächlich sehr einfach, ein solches Netzwerk zu finden, in dem genau eine Zeichenfolge fehlt. Die zu übersehende Zeichenfolge ist . Jetzt wollen Sie nur eine Schaltung, die die letzten Bits sortiert, und dann die ersten Bits. Diese Schaltung wird alles mit mindestens zwei sortiert s, wird offensichtlich Art des All-Null - String, und wird jede Zeichenfolge beginnend mit sortieren . $(1,0,\ldots,0)$ $n-1$ $n-1$ $1$ $0$

Andrew D. King
quelle

Kann das beispielhafte Sortiernetzwerk in Ihrer Antwort verallgemeinert werden, sodass Sie für eine bestimmte Zeichenfolge ein Sortiernetzwerk erstellen können, das diese Zeichenfolge falsch sortiert? Sie zeigen, wie es für eine bestimmte Saite gemacht wird, aber was ist mit anderen Saiten?

Sie können dies definitiv für jede Zeichenfolge mit einer Gewichtung von

oder

tun , aber ich bezweifle, dass es möglich ist, eine einzelne beliebige Bitfolge zu übersehen.

1

$1$

n - 1

$n-1$

Andrew D. King

OK, also sehe ich nicht, wie Ihre Antwort zeigt, dass die Antwort "Nein" ist. Die Konstruktion im zweiten Absatz Ihrer Antwort impliziert keine negative Antwort auf die ursprüngliche Frage, da es nur polynomiell viele Zeichenfolgen mit der Gewichtung

oder

. Es scheint, dass die ganze Arbeit in Ihrer Antwort durch den Verweis im Ian Parberry-Papier erledigt wird, aber dieser Satz im Parberry-Papier ist ziemlich vage, und ohne das Chung et al-Papier zu lesen, sehe ich nicht, wie wir daraus auf die Antwort schließen können zur frage steht "nein".

1

$1$

n - 1

$n-1$

Weitere Informationen: " Starke nicht deterministische Turingreduktion - eine Technik zum Nachweis der Unlösbarkeit " (Chung & Ravikumar) führt Folgendes als Lemma 2.1 auf: Bei einer nicht sortierten Zeichenfolge

gibt es ein polynomielles Sortiernetzwerk, das alle Zeichenfolgen mit Ausnahme von

korrekt sortiert . Für den Beweis bezieht es sich auf "Über die Größe von Testsets für Sortier- und verwandte Probleme" (Chung & Ravikumar), aber ich kann anscheinend keine Kopie des letzteren Papiers finden. Dies würde in der Tat bedeuten, dass die Antwort auf diese Frage "Nein" lautet.

x

$x$

x

$x$

Kristoffer Arnsfelt Hansen