Me presentan una red de comparación. ¿Cómo puedo determinar si la red de comparación es una red de clasificación? En la imagen a continuación hay un ejemplo de una red de clasificación de selección e inserción. La intención es tener una red de comparación y ordenar valores numéricos. Si pruebo 2 ^ n valores en este caso 2 ^ 8. Esta es una gran forma de trabajo no eficiente para probarlo. Estoy buscando un modelo / prueba matemático para verificar que esta sea una red de clasificación válida.

En general, verificar si una red de comparación particular es realmente una red de clasificación correcta es un problema completo de Co-NP. Si desea verificar mediante pruebas, debe probar exponencialmente muchas pruebas.

En particular, existen redes de clasificación que clasifican todos menos un valor correctamente, por lo que no puede esperar probar si la red es correcta o no simplemente al alimentarla con unas pocas entradas.

Un método estándar es probar si clasifica correctamente todas las entradas que están compuestas únicamente de ceros y unos. Si lo hace, resulta que ordenará todas las entradas (incluso las que no están limitadas a ceros y unas). Sin embargo, esto requiere exponencialmente muchas pruebas. Además, el número de pruebas no se puede reducir significativamente: para las entradas cero-uno, es posible demostrar que se necesitan al menos pruebas, hasta el punto de que la red de clasificación es correcta.$2^n$$2^n-n-1$

Alternativamente, uno puede usar pruebas donde las entradas son permutaciones de . Esto reduce un poco el número de pruebas necesarias, pero aún necesita exponencialmente muchas pruebas. En particular, las pruebas son necesarias y suficientes.$1,2,\dots,n$$C(n, \lfloor n/2 \rfloor)-1$

Para ver pruebas de estos hechos, consulte los siguientes documentos:

Sobre la complejidad computacional de la verificación óptima de la red de clasificación . Ian Parberry. Parle'91 Parallel Architectures and Languages ​​Europe, 1991.

Limita el tamaño de los conjuntos de prueba para la clasificación y las redes relacionadas . Moon Jung Chung y B. Ravikumar. Matemática discreta, vol 81, pp.1--9, abril de 1990.

Citando su pregunta:

Estoy buscando un modelo / prueba matemático para verificar que esta sea ​​una red de clasificación válida.

Si bien la respuesta (excelente) de DW se ocupa del caso general, consideraré su ejemplo específico. Se puede mostrar que una red de esta forma con entradas es una red de clasificación por inducción: (ver imagen para ilustración)$n$

1. $n=1$ entrada siempre se ordena;
2. Suponga que una red de tamaño de este formulario es una red de clasificación, y considere una red de tamaño . $n-1$$n$
   1. Más a la izquierda "en diagonal" siempre correctamente llevar el elemento más grande a la posición -ésimo (en su caso, );$n$$b_8$
   2. Te queda una red más pequeña y similar con los elementos restantes ;$n-1$
   3. Esta red más pequeña clasificará todos los elementos restantes por la hipótesis inductiva.

Cuando mira en una red de clasificación general, es posible que no tenga idea de cómo probar que ordena cada secuencia de valores (que tiene la longitud correcta para la red de clasificación) correctamente. Pero he aprendido sobre este buen truco, cómo simplificar la tarea:

El principio 0-1

Cuando una red de clasificación ordena todas las secuencias (con la longitud correcta) que consisten únicamente en "0" y "1" correctamente, entonces ordena cualquier secuencia (con la longitud correcta) correctamente. Por supuesto, "0" y "1" son marcadores de posición para cualquier elemento distinto en el dominio de la red de clasificación.

Entonces puedes construir una prueba como esta:

1. Tome dos elementos distintos del dominio de la red de clasificación y llámelos "0" y "1", de modo que "0" <"1"
2. Construya todas las cadenas binarias con la longitud exacta de la red de clasificación
3. En estas cadenas, sustituya el bit 0 y el bit 1 por "0" y "1"
4. Aplicar estas cadenas a la red de clasificación
5. Cada cadena debe clasificarse en algo así como 000..01 ... 1

Prueba de valores$2^n$

Para una prueba exhaustiva de una red de clasificación de longitud , generalmente tendría que probar todas las combinaciones de entrada. Pero con el principio 0-1 puede reducir esto a pruebas (probando todas las cadenas binarias de longitud ).$n$$2^n$$n$

¿Podemos hacerlo más barato?

Desafortunadamente, probablemente no podamos obtener mucho más barato que las pruebas exhaustivas, al menos no cuando se usa una máquina Turing para construir las pruebas. Por supuesto, cuando busca una red de clasificación específica, puede tener una idea creativa de cómo hacer una prueba simple. Pero en general, un algoritmo para construir tales pruebas es muy probable que sea tan complejo como probar todas las cadenas binarias. La razón de esto es que la red de clasificación de pruebas está relacionada con la clase de complejidad completa NP como se describe en las otras respuestas.

"Mucho más barato" en este contexto significa "tiempo polinómico". Es posible encontrar un algoritmo que pueda hacerlo "un poco" más rápido que el tiempo exponencial, pero que aún necesita más que el tiempo polinómico. Vea los comentarios para ver un ejemplo: Ejecutar en pasos es (ligeramente) más rápido que el tiempo exponencial pero aún (mucho) más lento que el tiempo polinómico.$2^{\sqrt n}$

Perspectiva / Perspectiva

¿Tu cerebro es una máquina de Turing

Una consecuencia filosófica es: cuando crees que puedes encontrar una prueba creativa de la exactitud de cada red de clasificación, también crees que tu cerebro probablemente no sea una máquina de Turing.

Clasificación paralela

El "principio 0-1" también se utiliza para comprobar la exactitud de los algoritmos de clasificación paralela. Tengo una (con suerte) buena presentación sobre esto en Github .

Corregir la red de clasificación

Si una de las cadenas está ordenada incorrectamente (por lo que ha demostrado que la red de clasificación es incorrecta), puede usar esto para construir una red de clasificación sin ese error. Simplemente agregue una comparación adicional sobre la posición del "borde 1-0" en la cadena de resultados incorrecta.