Suffit-il de trier pour plusieurs séquences 0-1 polynomiales pour un réseau de tri?

Le principe 0-1 dit que si un réseau de tri fonctionne pour toutes les séquences 0-1, alors il fonctionne pour n'importe quel ensemble de nombres. Existe-t-il un $S\subset \{0,1\}^n$ tel que si un réseau trie chaque séquence 0-1 de S, alors il trie chaque séquence 0-1 et la taille de $S$ est polynomiale en $n$ ?

Par exemple, si $S$ compose de toutes les séquences où il y a au plus $2$ exécutions (intervalles) de 1, alors y a-t-il un réseau de tri N et une séquence qui n'est pas ordonnée par N si tous les membres de $S$ sont ordonnés par N?

Réponse: Comme on peut le voir dans la réponse et les commentaires, la réponse est que pour chaque chaîne non triée, il existe un réseau de tri qui trie toutes les autres chaînes. Une simple preuve en est la suivante. Soit la chaîne $s=s_1\ldots s_n$ telle que $s_i=0$ pour toujours $i<k$ et . Puisque n'est pas trié, après le tri, doit être à . Comparez avec chaque pour lequel . Comparez ensuite chaque paire telle sorte que $s_k=1$ $s$ $s_k$ $0$ $k$ $i$ $s_i=1$ $(i,j)$ $i\ne k$ et plusieurs fois. Cela laisse la chaîne entière triée, sauf peut-être pour $j\ne k$ , qui n'est pas trié pour , et pour certaines autres chaînes qui ont plus de que . Maintenantcomparez pour downto sauf pour le lieu où devrait aller . Cela triera tout sauf l' . $s_k$ $s$ $1$ $s$ $s_k$ $i=n$ $1$ $s_k$ $s$ $s$

Mise à jour: je me demande ce qui se passe si nous limitons la profondeur du réseau à . $O(\log n)$

ds.algorithms sorting sorting-network domotorp
la source

Il semble que ce soit possible , vous devez limiter la taille du réseau de tri pour être plus petit que la taille

. Sinon, le réseau ne pourrait-il pas simplement vérifier si l'entrée est l'un des éléments de

et agir correctement dans l'affirmative, sinon agir incorrectement?

S

$S$

S

$S$

usul

@usul: Je ne pense pas qu'un réseau de tri puisse vérifier une telle chose. Quoi qu'il en soit, il est naturel de travailler avec des réseaux de tri dont la taille est polynomiale en

n

$n$

domotorp

Réponses:

Il semble que non. Ian Parberry fait référence à un article de Chung et Ravikumar, où ils supposent une construction récursive d'un réseau de tri qui trie toutes les chaînes de bits sauf une, et déduisent en outre que le problème de la vérification d'un réseau de tri est - complet. Je ne trouve pas le papier original tout de suite, mais il correspond certainement à (mon) intuition. $co$ $NP$

Modifier pour ajouter: Il est en fait très facile de trouver un tel réseau qui manque exactement une chaîne. La chaîne à manquer sera . Maintenant, vous voulez juste un circuit qui trie les derniers bits, puis trie les premiers bits. Ce circuit triera n'importe quoi avec au moins deux s, triera évidemment la chaîne entièrement nulle et triera toute chaîne commençant par . $(1,0,\ldots,0)$ $n-1$ $n-1$ $1$ $0$

Andrew D. King
la source

L'exemple de réseau de tri dans votre réponse peut-il être généralisé, de sorte que pour une chaîne donnée, vous pouvez construire un réseau de tri qui mal trie cette chaîne? Vous montrez comment le faire pour une chaîne particulière, mais qu'en est-il des autres chaînes?

Vous pouvez certainement le faire pour n'importe quelle chaîne de poids

, mais je doute qu'il soit possible de manquer une seule chaîne de bits arbitraire.

1

$1$

n - 1

$n-1$

Andrew

OK, donc je ne vois pas comment votre réponse montre que la réponse est "Non". La construction dans le deuxième paragraphe de votre réponse n'implique pas une réponse négative à la question d'origine, car il n'y a que de nombreuses chaînes polynomiales de poids

. Il semble que tout le travail dans votre réponse soit fait par la référence dans le papier Ian Parberry, mais cette phrase dans le papier Parberry est plutôt vague et sans lire le papier Chung et al je ne vois pas comment nous pouvons conclure que la réponse à la question est "Non".

1

$1$

n - 1

$n-1$

Plus de sleuthing: " Forte réduction non déterministe de Turing - une technique pour prouver l'intractabilité " (Chung & Ravikumar) énumère ce qui suit comme Lemme 2.1: étant donné toute chaîne non triée

, il existe un réseau de tri de taille polynomiale qui trie toutes les chaînes correctement sauf

. Pour la preuve, il se réfère à "Sur la taille des ensembles de test pour le tri et les problèmes connexes" (Chung & Ravikumar), mais je n'arrive pas à trouver une copie de ce dernier papier. Cela impliquerait en effet que la réponse à cette question est "non".

x

$x$

x

$x$

Document de Chung & Ravikumar

Kristoffer Arnsfelt Hansen