On the Complexity of Completing Binary Predicates
share
Given a binary predicate P, the length of the smallest program that computes a complete extension of P is less than the size of the domain of P plus the amount of information that P has with the halting sequence. This result is derived from a theorem in this paper which says a prefix free set with large M measure will have small monotone complexity, Km.
READ FULL TEXT