Skip to main content

certified_incompressible_function_exists

Function certified_incompressible_function_exists 

Source
pub fn certified_incompressible_function_exists(n: u32) -> Option<CountingCert>
Expand description

A kernel-re-checkable counting certificate that an incompressible Boolean function on n variables MUST exist. A function is its 2ⁿ-bit truth table, and there are only 2^{2ⁿ} − 1 programs shorter than 2ⁿ bits — too few to name all 2^{2ⁿ} functions — so at least one has no shorter description. This is the certified REASON the census residue is nonempty: boolean_function_census measures it, counting guarantees it. Any such function necessarily sits in the residue (no arsenal compresses the truly incompressible). None for n = 0 or n > 6 (a 2⁷-bit truth table overflows the exact-u128 counting range). Re-check with crate::pigeonhole::check_counting_cert.