Muchos resultados en criptografía dependen de resultados / conjeturas imposibles en la teoría de la complejidad. Por ejemplo, se cree que la criptografía de clave pública que usa RSA es posible debido a la conjetura sobre la inviabilidad de la factorización (y los problemas de búsqueda de raíz modular).
Mi pregunta es :
¿Tenemos resultados similares en la teoría de la computabilidad? ¿Hay construcciones positivas interesantes que usan resultados de imposibilidad negativos?
Por ejemplo, ¿la indecidibilidad del problema de detención nos permite realizar tareas que no podríamos hacer si el problema de detención fuera decidible?
Respuestas:
En cierto sentido, de esto se trata la teoría de la parametricidad.
La abstracción de datos es cómo nos aseguramos de que ningún cliente de un módulo pueda acceder a los elementos de un módulo, excepto de acuerdo con la interfaz expuesta por el módulo. Confiamos en esto para garantizar que los clientes de un módulo no puedan romper los invariantes internos de las estructuras de datos; por ejemplo, si accede a un árbol equilibrado solo a través de la interfaz publicada, se deduce que el árbol siempre estará equilibrado.
Por lo tanto, utilizamos una propiedad negativa, que ningún cliente posible puede romper el límite de abstracción, para deducir una positiva, que la representación de datos siempre tiene.
fuente
La complejidad de Kolmogorov podría caer en esta categoría.
Se puede demostrar que hay ciertas cadenas que no pueden ser comprimidas por ninguna máquina de Turing. Estas cadenas se comportan "genéricamente" para que pueda estudiar las propiedades aleatorias de cierta información y tareas computacionales al estudiar el comportamiento con respecto a una cadena incompresible (no aleatoria).
fuente