Why is sorting pancakes NP hard?

Solution 1:

They are saying exactly that - it's easy to see that any stack can be flipped in $2n-1$ flips as you point out, but the question is, what's the precise bound? It does have to be roughly linear by a counting argument ($k$ flips can only bring about $O(n^k)$ configurations and there are $n!\approx n^ne^{-n}$ configurations of $n$ pancakes), but getting the precise constant on the linear term is harder than it appears. The Wikipedia page suggests that the constant is between $15/14$ and $18/11$, better than your naive $2n$ approach.

It's almost more surprising that the problem has been open this long - for instance, many efficiently-solvable puzzles such as the $15$ puzzle have 'easy' solutions but hard bounds on finding optimal solutions. Finding optimal configurations is often hard, and it's not surprising that it's hard here.