The width of a classical planning instance, among other metrics, indicates the computational difficulty of the instance. However, no result exists on the complexity of computing the width itself. In this paper, we address this by utilising an optimisation complexity framework. We focus on planning instances with polynomially bounded solutions, and prove that computing their width is OptP[O(log log L)]-hard, where L is the size of the instance. In turn, for the upper bound, we show that computing width is in OptP[O(log L)]^OptP[O(log L)]. These results contribute to the understanding of width as a proxy measure for the computational difficulty of planning, and suggest that exploiting other structural restrictions beyond bounding solution length can provide further insights on the complexity of width computation.