Why are these geometric problems so hard?

Question

I was surprised to learn that both for the Moving Sofa Problem and Packing 11 Squares solutions have been proposed, but in either case the optimality of the proposed solution is, as of yet, only conjectured. At first glance, these problems appear "innocent" to me, but presumably deceptively so. (Rest assured: I don't have clue on how to approach either of them.)

What is the nature of the presumed hurdle that needs to be taken here to prove optimality? Is the issue some kind of computational complexity that needs to be overcome, does it require some technique that as of yet is unknown, does the optimality hinge on some other conjectures, ...? Or is this something we don't and cannot know until it actually has been done?

I realize that these are two different problems, but, I thought, perhaps unwisely, to put them in one question. Perhaps they share a difficulty that is shared by many such problems and still is rather specific to such problems.

---

^{Further references: Moving Sofa Problem on Wikipedia, Moving Sofa Problem on MathWorld, Gerver solution to the Moving Sofa Problem (pdf), Packing 11 Squares on MathWorld}

---

I include an animated image by Claudio Rocchini of (unfortunately) a non-optimal solution to the first problem. Just because it looks good.

Answer 1

This is an inadequate answer, but...

These problems are difficult because (a) the space of possible solutions is vast, and (b) there seems insufficient structure to reduce the space so that searching it becomes feasible.

Consider the 11-squares problem. Each square has a location and an orientation, and so can be pinned down by specifying three parameters. So 33 parameters determine a configuration of 11 squares, and so determine the surrounding square. But this means one is, in a sense, searching a 33-dimensional space for the optimal solution.

Of course, there are many constraints that make this 33 an overestimate. (For example, the first square can be constrained to, say, $(0,0){-}(1,1)$, so it is really "only" a 30-dimensional space...) But when you see a packing like that shown below (due to Károly Hajba), your confidence in constraining the parameters is shaken.

     
     _{(A packing of 51 squares. Image from this link.)}