Supongo que se está refiriendo al resultado de que resolver la unicidad del elemento requiere tiempo Omega (n log n) en el modelo basado en la comparación.
La reducción que busca no existe. No puede tomar un cuadro negro que resuelva la unicidad del elemento y usarlo para ordenar. La salida del cuadro negro de “unicidad del elemento” es prácticamente inútil si realmente desea ordenar la entrada.
Hay pruebas similares para otros problemas que usan reducciones. Un ejemplo canónico es el casco convexo . Encontrar un casco convexo es al menos tan difícil como clasificar los reales. Esto se puede probar usando una reducción (más precisamente, una reducción de Turing en tiempo O (n), en este caso): puede reducir la clasificación de reales para encontrar un casco convexo 2D tomando los números que desea ordenar, escalando dentro del rango [0,2pi] e interpretándolos como coordenadas polares de puntos en un círculo unitario. El orden en que se encuentran los puntos en el casco convexo corresponde al orden ordenado de los números originales.
- ¿Son dos semanas suficientes para terminar un pequeño proyecto de aprendizaje automático?
- ¿Cuál es la diferencia entre un archivo y un documento en una computadora?
- ¿Google está bajando su barra de contratación para ingenieros?
- ¿Existe una simulación por computadora para cuestiones económicas y sociales?
- ¿Cómo encuentro una pasantía en una empresa tecnológica francesa?
Por otro lado, la prueba de que la unicidad del elemento es difícil en el modelo basado en la comparación (y también en varios modelos un poco más potentes) utiliza una técnica ligeramente diferente: tomamos cualquier algoritmo que resuelva la unicidad del elemento y lo demostramos cuando termina con una respuesta negativa, ya debe haber adquirido suficiente información para conocer el orden de todos los elementos.
Pero una vez que sepa que la propiedad anterior se mantiene, puede acercarse decentemente a tener una reducción. Supongamos que desea ordenar n elementos distintos , y alguien le dio un algoritmo correcto que resuelve la unicidad del elemento. Luego, puede ejecutar ese algoritmo (hasta que finalice y envíe el mensaje de que no hubo duplicados), registre las comparaciones que realizó y, al final, utilice la ordenación topológica para reconstruir el orden ordenado de todos los elementos.
Aún así, tenga en cuenta que lo que describí anteriormente técnicamente no es una reducción en el sentido habitual.
