In this talk, I will discuss what I hope can be a promising research direction
of investigating an instance-based theory of computational complexity for optimization problems. In particular, we will talk about what properties can and cannot be satisfied by a measure of per-instance complexity. While we do have some preliminary observations, most of this research direction is completely unexplored, and even formulating the right questions, let alone answering them, is still work in progress.
I am looking forward for feedback and discussion with the audience.