Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Search-to-decision for compression.

Proved
CompressionOWF.decisionToFinder_correct

by raver1975 · Sep 13, 2026 · Mathlib c5ea003 (Lean v4.30.0)

aether-catalogspeculative

Search-to-decision for compression. A correct decision oracle for the conditional predicate "some length-n continuation of w is a D-program for y" yields a shortest-program finder for D, provided the fuel covers the complexity.

theorem CompressionOWF.decisionToFinder_correct(D : Str → Str) (dec : Str → Str → ℕ → Bool)
    (fuel : ℕ → ℕ)
    (hdec : ∀ y w n, dec y w n = true ↔ ∃ p : Str, p.length = n ∧ D (w ++ p) = y)
    (y : Str) (hy : Describable D y) (hfuel : K D y ≤ fuel y.length) :
    D (decisionToFinder dec fuel y) = y ∧
      (decisionToFinder dec fuel y).length = K D y := by sorry

Formalization Note Transplanted verbatim from the Aether Catalog source Speculative/AutoResearch/CompressionSearchToDecision.lean; the statement is byte-identical to the source declaration, elaborated with autoImplicit disabled in the platform environment.

Preamble
-- Thm stub generated from Speculative/AutoResearch/CompressionSearchToDecision.lean
import Mathlib
import Definitions.Def_Speculative_AutoResearch_CompressionOneWayFunctions
import Definitions.Def_Speculative_AutoResearch_CompressionSearchToDecision
import Definitions.Def_Speculative_AutoResearch_CompressionUniversality
/-
Copyright (c) 2025. All rights reserved.

# Search-to-Decision for Compression, and its Cryptographic Payoff

## Overview

Third cycle of the Phase-B/M8 investigation (`Shared.CompressionOneWayFunctions`,
`Shared.CompressionUniversality`).

The previous cycles compared two *search* tasks — inverting a function and
finding shortest programs — and proved them equivalent.  The literature on
polynomial-time Kolmogorov complexity phrases hardness assumptions instead in
terms of the *decision* problem "is `K(y) ≤ n`?" (MINKT), so a complete
characterization must bridge search and decision.  That bridge is the classical
bit-by-bit prefix reconstruction, which we formalize here:

* `rebuild` — reconstruct a program one bit at a time from a *decision* oracle
  for the conditional predicate "some length-`n` continuation of the prefix `w`
  is a program for `y`";
* `rebuild_correct` — the reconstruction returns a genuine program of exactly the
  promised length (proved by induction on the number of remaining bits);
* `decisionToFinder_correct` — combining the reconstruction with the bounded
  search of `leastFrom` turns the decision oracle into a *shortest*-program
  finder;
* `decision_solves_inversion` — hence into an inverter;
* `owf_no_prefix_decider` — **cryptographic payoff**: if `f` is one-way for a
  class, then no algorithm of the class can decide the prefix-compressibility
  predicate of `f`.  The decision version of compression is hard exactly when
  one-way functions exist.

Together with cycle 1 (search version) and cycle 2 (approximate version), this
gives the promised map: *validity, exact-shortest, approximate-shortest and
prefix-decision compression tasks all sit at the same cryptographic level.*

No axioms beyond the standard three, no `sorry`.
-/

open CompressionOWF

/-! ## Section 1: Bit-by-bit reconstruction from a decision oracle -/



/-! ## Section 2: From the decision oracle to a shortest-program finder -/
Formal statement
theorem CompressionOWF.decisionToFinder_correct(D : Str → Str) (dec : Str → Str → ℕ → Bool)
    (fuel : ℕ → ℕ)
    (hdec : ∀ y w n, dec y w n = true ↔ ∃ p : Str, p.length = n ∧ D (w ++ p) = y)
    (y : Str) (hy : Describable D y) (hfuel : K D y ≤ fuel y.length) :
    D (decisionToFinder dec fuel y) = y ∧
      (decisionToFinder dec fuel y).length = K D y := by sorry
Source
https://github.com/paulklemstine/Lean/blob/53c2925a02/Catalog/Speculative/AutoResearch/CompressionSearchToDecision.lean#L110

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me