Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

An article posted yesterday (http://www.i-programmer.info/news/112-theory/3280-pancake-flipping-is-hard-np-hard.html) references a new study released on Arxiv (http://arxiv.org/abs/1111.0434v1) with the following summary:

Pancake Flipping is the problem of sorting a stack of pancakes of different sizes (that is, a permutation), when the only allowed operation is to insert a spatula anywhere in the stack and to flip the pancakes above it (that is, to perform a prefix reversal). In the burnt variant, one side of each pancake is marked as burnt, and it is required to finish with all pancakes having the burnt side down. Computing the optimal scenario for any stack of pancakes and determining the worst-case stack for any stack size have been challenges over more than three decades. Beyond being an intriguing combinatorial problem in itself, it also yields applications, e.g. in parallel computing and computational biology. In this paper, we show that the Pancake Flipping problem, in its original (unburnt) variant, is NP-hard, thus answering the long-standing question of its computational complexity.

The premise is that we don't even know the upper bound maximum for number of flips for a stack any larger than 19. The instant I read this, I had the solution, and I want you to tell me why I am wrong.

The maximum number of flips for any stack is 2 * (number of items - 1), and it is a supremely trivial algorithm to implement.

The process is only a single one-or-two-flip step repeated until completion:

  • Division point is directly beneath the largest unsorted pancake (unless its on top)
  • Flip one brings it to the top (unless its on top)
  • Division point #2 is directly above the largest properly sorted pancake
  • Flip two properly sorts another pancake

From the PDF:

Figure 1: Examples of efficient flips. Sequence 5; 2; 3; 1; 4 is efficiently sortable (in four flips), but 5; 2; 3; 4; 1 is not.

I beg to differ...
52314. The steps with this approach are: 41325, 23145, 32145, 12345.
52341. The steps with this approach are: 14325, 41325, 23145, 32145, 12345.
Are they really saying that 4 is efficient but 5 is not?

share|improve this question
1  
"Efficiently sortable," as defined in the paper (did you read the definition?) is not a statement about how many moves are needed to sort a sequence. It is a statement about whether a sequence can be sorted using moves that are "efficient" in a technical sense defined in the paper. Your flips on 52341 don't satisfy that condition. –  Nate Eldredge Nov 4 '11 at 20:44
1  
I suggest that you read the definitions immediately following Property 1 on page 3: they explain exactly why $\langle 5,2,3,4,1\rangle$ is not efficiently sortable as that notion is defined. –  Brian M. Scott Nov 4 '11 at 20:49
add comment

1 Answer

up vote 8 down vote accepted

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.

share|improve this answer
    
Regarding §2: the prefix constraint made it more difficult to find a hardness proof -- not that the unconstrained version was "trivially" hard either. I'm curious to see which category the signed version will turn out to belong to. Congratulations to the authors! –  Anthony Labarre Nov 5 '11 at 0:05
    
Thanks. I knew there was more to it, just had to ask. –  Fosco Nov 5 '11 at 4:30
    
@AnthonyLabarre : Oh, I don't mean to imply that the result was trivial - obviously it's excellent work on the authors' part! Just that if you'd asked whether finding an optimal solution was going to be hard or easy, I think most of the money would've been on hard. That doesn't make proving it any less impressive a feat, though! –  Steven Stadnicki Nov 5 '11 at 18:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.