¿Es suficiente ordenar polinomialmente muchas secuencias 0-1 para una red de clasificación?

El principio 0-1 dice que si una red de clasificación funciona para todas las secuencias 0-1, entonces funciona para cualquier conjunto de números. ¿Hay una tal que si una red ordena cada secuencia 0-1 de S, entonces ordena cada secuencia 0-1 y el tamaño de es polinomial en ? $S\subset \{0,1\}^n$ $S$ $n$

Por ejemplo, si consiste en todas las secuencias donde hay como máximo carreras (intervalos) de 1, entonces ¿hay una red de clasificación N y una secuencia que no está ordenada por N si todos los miembros de están ordenados por N? $S$ $2$ $S$

Respuesta: Como se puede ver en la respuesta y en los comentarios, la respuesta es que para cada cadena sin clasificar hay una red de clasificación que clasifica todas las demás cadenas. Una prueba simple de esto es lo siguiente. Deje que la cadena sea tal que para siempre y . Como no está ordenado, después de ordenar debería ser . Compare con cada para la cual . Luego compare cada par modo que $s=s_1\ldots s_n$ $s_i=0$ $i<k$ $s_k=1$ $s$ $s_k$ $0$ $k$ $i$ $s_i=1$ $(i,j)$ $i\ne k$ y muchas veces. Esto deja toda la cadena ordenada, excepto posiblemente por , que no está ordenada por , y por ciertas otras cadenas que tienen más 's que . Ahora compare para downto excepto el lugar donde debería ir en . Esto ordenará todo menos . $j\ne k$ $s_k$ $s$ $1$ $s$ $s_k$ $i=n$ $1$ $s_k$ $s$ $s$

Actualización: Me pregunto qué sucede si restringimos la profundidad de la red a . $O(\log n)$

ds.algorithms sorting sorting-network domotorp
fuente

Parece que a ser posible se debe restringir el tamaño de la red de clasificación para ser más pequeño que el tamaño de

. De lo contrario, ¿no podría la red simplemente verificar si la entrada es uno de los elementos de

y actuar correctamente si es así, de lo contrario, actuar incorrectamente?

S

$S$

S

$S$

usul

@usul: No creo que una red de clasificación pueda verificar tal cosa. De todos modos, es natural trabajar con redes de clasificación cuyo tamaño es polinómico en

n

$n$

domotorp

Respuestas:

Parece que no. Ian Parberry hace referencia a un artículo de Chung y Ravikumar, donde supuestamente dan una construcción recursiva de una red de clasificación que ordena cada cadena de bits pero uno, y además deducir que el problema de la verificación de una red de clasificación es - completo. No puedo encontrar el documento original de inmediato, pero ciertamente coincide con (mi) intuición. $co$ $NP$

Editar para agregar: en realidad, es muy fácil encontrar una red que pierda exactamente una cadena. La cadena que se perderá será . Ahora solo desea un circuito que clasifique los últimos bits, luego clasifique los primeros bits. Este circuito clasificará cualquier cosa con al menos dos s, obviamente clasificará la cadena de todo cero y clasificará cualquier cadena que comience con . $(1,0,\ldots,0)$ $n-1$ $n-1$ $1$ $0$

Andrew D. King
fuente

¿Se puede generalizar el ejemplo de la red de clasificación en su respuesta, de modo que para cualquier cadena dada, pueda construir una red de clasificación que clasifique mal esa cadena? Muestra cómo hacerlo para una cadena en particular, pero ¿qué pasa con otras cadenas?

Definitivamente puede hacerlo para cualquier cadena de peso

, pero dudo que sea posible perder una sola cadena de bits arbitraria.

1

$1$

n - 1

$n-1$

Andrew D. King

Bien, no veo cómo su respuesta muestra que la respuesta es "No". La construcción en el segundo párrafo de su respuesta no implica una respuesta negativa a la pregunta original, ya que solo hay polinomialmente muchas cadenas de peso

. Parece que todo el trabajo en su respuesta está siendo hecho por la referencia en el artículo de Ian Parberry, pero esa oración en el documento de Parberry es bastante vaga y sin leer el documento de Chung et al no veo cómo podemos concluir que la respuesta a la pregunta es "No".

1

$1$

n - 1

$n-1$

Más investigación: " Fuerte reducción no determinista de Turing: una técnica para demostrar la intratabilidad " (Chung y Ravikumar) enumera lo siguiente como Lema 2.1: dada cualquier cadena no clasificada

, existe una red de clasificación de tamaño polinómico que clasifica todas las cadenas correctamente excepto

. Para la prueba se refiere a "Sobre el tamaño de los conjuntos de prueba para la clasificación y problemas relacionados" (Chung y Ravikumar), pero parece que no puedo encontrar una copia del último documento. Esto implicaría que la respuesta a esta pregunta es "No".

x

$x$

x

$x$

Ponencia de Chung y Ravikumar

Kristoffer Arnsfelt Hansen