I was looking for the computational complexity of the Mutilated Chessboard Problem waiting to find an upper bound in order to know which category of complexity the problem belonged to.
What i found is instead a paper where the author proves an exponential lower bound for this problem. Is specificing lower bound a way to show that the problem belongs to a certain complexity's category (NP-Hard in this case) ?