método de incompresibilidad
En matemáticas , el método de incompresibilidad es un método de prueba como el método probabilístico , el método de conteo o el principio del casillero . Para probar que un objeto en cierta clase (en promedio) satisface cierta propiedad, seleccione un objeto de esa clase que sea incompresible . Si no satisface la propiedad, se puede comprimir mediante cálculocodificación. Dado que generalmente se puede probar que casi todos los objetos en una clase dada son incompresibles, el argumento demuestra que casi todos los objetos en la clase tienen la propiedad involucrada (no solo el promedio). Seleccionar un objeto incompresible es ineficaz y no se puede hacer con un programa de computadora. Sin embargo, un argumento de conteo simple generalmente muestra que casi todos los objetos de una clase determinada pueden comprimirse solo unos pocos bits (son incompresibles).
El método de la incompresibilidad depende de una noción objetiva y fija de incompresibilidad. Tal noción fue proporcionada por la teoría de la complejidad de Kolmogorov , llamada así por Andrey Kolmogorov . [1]
Uno de los primeros usos del método de incompresibilidad con la complejidad de Kolmogorov en la teoría de la computación fue demostrar que el tiempo de ejecución de una máquina de Turing de una cinta es cuadrático para aceptar un lenguaje palindrómico y los algoritmos de clasificación requieren al menos tiempo para clasificar elementos. [2] Uno de los primeros artículos influyentes que utilizaron el método de incompresibilidad se publicó en 1980. [3] El método se aplicó a varios campos y su nombre se acuñó en un libro de texto. [4]
