Proof of Thm A.4, p. A:42 —
ProvedObfImpossibility.RiceNoSize.KC_le_sizecomputabilitykolmogorov-complexityp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every machine , the size of the smallest machine computing the same function as is at most the size of :
The proof of Theorem A.4 uses this inequality to show that the decider , which only tries the inputs , finds the input witnessing .
Preamble
import Mathlib import Definitions.Def_ObfImpossibility_RiceNoSize_ProofObjects
Formal statement
namespace ObfImpossibility.RiceNoSize /-- p. A:42: `KC([M]) ≤ |M|` for every machine `M`. -/ theorem KC_le_size (M : Machine) : KC (fn M) ≤ size M := by sorry end ObfImpossibility.RiceNoSize
Source
Barak et al., On the (Im)possibility of Obfuscating Programs, J. ACM 59(2) (2012), author's copy, p. A:42, proof of Theorem A.4 ("x < KC([M]) ≤ |M|")
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.