2
$\begingroup$

The so-called Pancake flipping problem first discussed by Jacob E. Goodman here yields two entangled problems:

  1. MIN-SBPR (Sorting By Prefix Reversals) - Given a permutation, find the smallest sequence of flips sorting the permutation.
  2. Compute $f(n)$ - For a given $n \in \mathbb{N}$, what is the maximum number of flips required to sort any permutation of size $n$?

This paper shows that the first problem is NP-hard.

Now, my question is: Is it known whether the second problem is NP-hard as well? Is there any paper on the NP-hardness of the second problem?

For me, it seems like the second problem is kind of stronger than the first one. Does the NP-hardness of that one follow from the first one in some way? You cannot just check each permutation using the first one since there are $n!$ many permutations.

Improve this question
$\endgroup$
9
  • 3
    $\begingroup$ If I'm reading the definitions correctly, $f$ is OEIS A058986. There are sufficiently many references there that I haven't tried to skim them all for discussion of complexity, but the hard tag and the small number of entries suggest that it's plausible that the problem is NP-hard. $\endgroup$
    – Peter Taylor
    Commented Feb 20, 2023 at 16:52
  • $\begingroup$ Yes, the OEIS is correct, you can also find it here. I also think that is should be NP-hard but I wonder if it was proven yet. $\endgroup$
    – borekking
    Commented Feb 20, 2023 at 17:08
  • 4
    $\begingroup$ The second one doesn't follow from the first one in any simple way. For example, it is conceivable that for every $n$, it is easy to identify a worst-case permutation and determine how many flips it requires, even though an arbitrary permutation is hard to analyze. (I doubt that this is actually true, but the point is that there's no simple way to rule it out.) $\endgroup$
    – Timothy Chow
    Commented Feb 21, 2023 at 2:48
  • 1
    $\begingroup$ Your question is a bit confused. You are asking if some sequences is easily computable. Do you mean $n$ in unary of in binary? Why are you thinking of NP-hardness, not #P-hardness which is more appropriate for a counting problem? Do you know any sequence which is NP-hard to compute? If you don't have good answers to these questions, you might like to read my ICM paper first: math.ucla.edu/~pak/papers/ICM-paper9.pdf $\endgroup$
    – Igor Pak
    Commented Feb 21, 2023 at 3:03
  • 1
    $\begingroup$ Problems that take an integer as an input are rarely NP-hard, see cstheory.stackexchange.com/questions/14124/… $\endgroup$
    – domotorp
    Commented Feb 21, 2023 at 5:28

0

Reset to default

You must log in to answer this question.