Metraipolis › archive › dc_b043bf1ade5f
Incompressibility method — Wikipedia (en)
- Source
- Wikipedia (en)
- Original
- https://en.wikipedia.org/wiki/Incompressibility_method
- License (as archived)
- CC-BY-SA-4.0
- Archived
- 2026-10-07T22:24:52.446Z
- SHA-256 of the archived text
d54891b91a199cf4a17f8183552a0fdcc9d4b4629382c1d40cad6680cf7291a2- Stable URL of this page
https://metraipolis.com/documento/dc_b043bf1ade5f
How to cite
Incompressibility method — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Incompressibility_method (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_b043bf1ade5f (Metraipolis archive dc_b043bf1ade5f, sha256 d54891b91a199cf4a17f8183552a0fdcc9d4b4629382c1d40cad6680cf7291a2)
BibTeX
@misc{dcb043bf1ade5f,
title = {Incompressibility method — Wikipedia (en)},
howpublished = {Wikipedia (en)},
url = {https://en.wikipedia.org/wiki/Incompressibility_method},
note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_b043bf1ade5f; sha256 d54891b91a199cf4a17f8183552a0fdcc9d4b4629382c1d40cad6680cf7291a2},
year = {2026}
}Archived text
Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Incompressibility_method. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
In mathematics, the incompressibility method is a proof method like the probabilistic method, the counting method or the pigeonhole principle. To prove that an object in a certain class (on average) satisfies a certain property, select an object of that class that is incompressible. If it does not satisfy the property, it can be compressed by computable coding. Since it can be generally proven that almost all objects in a given class are incompressible, the argument demonstrates that almost all objects in the class have the property involved (not just the average). To select an incompressible object is ineffective, and cannot be done by a computer program. However, a simple counting argument usually shows that almost all objects of a given class can be compressed by only a few bits (are incompressible). Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «combinatorics»). Fonte: Wikipedia in inglese, voce «Incompressibility method» — https://en.wikipedia.org/wiki/Incompressibility_method Wikidata Q25304532 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q25304532 Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Incompressibility_method?action=history). Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza. Estratto dell'introduzione non modificato nel contenuto; revisione 1369485509, consultata il 2026-10-07T22:05:42.046Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: a5c3927b0c9fa7f842552ae447a8e285c5f3284e95e60655b1529ec5884c6e89