Another naive thing to do is ask about the length of the program required to get from one program to another, in various ways.
Given an oracle for p1, what’s the complexity of the output of p2?
What if you had an oracle for all the intermediate states of p1?
What if instead of measuring the complexity, you measured the runtime?
What if instead of asking for the complexity of the output of p2, you asked for the complexity of all the intermediate states?
All of these are interesting but bad at being metrics. I mean, I guess you could symmetrize them. But I feel like there’s a deeper problem, which is that they by default ignore computational process, and have to have it tacked as extra.
Another naive thing to do is ask about the length of the program required to get from one program to another, in various ways.
Given an oracle for p1, what’s the complexity of the output of p2?
What if you had an oracle for all the intermediate states of p1?
What if instead of measuring the complexity, you measured the runtime?
What if instead of asking for the complexity of the output of p2, you asked for the complexity of all the intermediate states?
All of these are interesting but bad at being metrics. I mean, I guess you could symmetrize them. But I feel like there’s a deeper problem, which is that they by default ignore computational process, and have to have it tacked as extra.