 Levin complexity The Levin complexity of a string x is the sum of the length \(\cal{l}(p)\) and the logarithm of the computation time of the smallest program p that produces x when it runs on a universal Turing machine U, noted as \(U(p)=x\): 