Note that this only proves the minimum complexity in the system used to run this operation; it could have a different complexity in a different system.
[ETA]: Also, I think this runs into the Chaitin issue. (Personally, I think the issue is with the flawed definition of “complexity” such that it incorporates only the size of the reference, and not the processing power necessary to disentangle the target from the reference.)
Note that this only proves the minimum complexity in the system used to run this operation; it could have a different complexity in a different system.
[ETA]: Also, I think this runs into the Chaitin issue. (Personally, I think the issue is with the flawed definition of “complexity” such that it incorporates only the size of the reference, and not the processing power necessary to disentangle the target from the reference.)