I agree that’s a more interesting question, and computational complexity theorists have done work on it which I don’t fully understand, but it also doesn’t seem as relevant for AI safety questions.
You should probably also talk to computability/recursion theorists, who can put problems on scales of complexity mirroring the polynomial and exponential time hierarchies that define complexity theory.
I agree that’s a more interesting question, and computational complexity theorists have done work on it which I don’t fully understand, but it also doesn’t seem as relevant for AI safety questions.
True, it’s not that relevant.
You should probably also talk to computability/recursion theorists, who can put problems on scales of complexity mirroring the polynomial and exponential time hierarchies that define complexity theory.