Feb 21, 2012 - Pancakes we are given a stack of pancakes, all of different sizes. L. Bulteau ..... Lock 3 states: closed
Pancake Flipping Is Hard
Laurent BULTEAU, Guillaume FERTIN, Irena RUSU LINA, Université de Nantes
Feb. 21st, 2012
Pancake Flipping Problem
L. Bulteau
Pancake Flipping Is Hard
2/28
Pancakes we are given a stack of pancakes, all of different sizes
L. Bulteau
Pancake Flipping Is Hard
3/28
Pancakes we are given a stack of pancakes, all of different sizes we want to rearrange it into a beautiful pyramidal stack
L. Bulteau
Pancake Flipping Is Hard
3/28
Pancakes we are given a stack of pancakes, all of different sizes we want to rearrange it into a beautiful pyramidal stack we have a spatula, to flip the top of the stack
L. Bulteau
Pancake Flipping Is Hard
3/28
Pancakes we we we we
L. Bulteau
are given a stack of pancakes, all of different sizes want to rearrange it into a beautiful pyramidal stack have a spatula, to flip the top of the stack are lazy
Pancake Flipping Is Hard
3/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
Pancakes Example
L. Bulteau
Pancake Flipping Is Hard
4/28
The problem to be solved
Problem Given a stack of n pancakes, how can it be arranged with as little effort as possible?
L. Bulteau
Pancake Flipping Is Hard
5/28
Other points of view
“Pancake view” Given a stack of n pancakes, how can it be arranged with as little effort as possible?
Formal problem : MIN-SBPR Given a permutation π of {1, . . . , n}, compute the prefix reversal distance between π and the Identity, written prd (π).
“Biology view” Given two genomes using the same n genes, how many steps have been used in evolution between one and the other?
L. Bulteau
Pancake Flipping Is Hard
6/28
Other points of view
Pancakes Pancake Stack
L. Bulteau
Formal Integer Permutation
Pancake Flipping Is Hard
Biology Gene Genome
7/28
Other points of view
Pancakes Pancake Stack Nice stack Flip
L. Bulteau
Formal Integer Permutation Identity Prefix reversal
Pancake Flipping Is Hard
Biology Gene Genome Reference genome Evolution step
7/28
Other points of view
Pancakes Pancake Stack Nice stack Flip We are lazy
L. Bulteau
Formal Integer Permutation Identity Prefix reversal Minimization formulation (distance)
Pancake Flipping Is Hard
7/28
Biology Gene Genome Reference genome Evolution step Parsimony principle
Pancake Problem
Complexity: NP-complete Related results: Reversal distance, not necessarily prefix: NP-complete (APX-hard) for unsigned permutations, polynomial for signed permutations.
Burnt pancakes variant, or Prefix Reversal Distance for signed permutations: complexity unknown.
Algorithms: polynomial-time algorithm for a subclass of signed permutations (simple permutations [Labarre, Cibulka, 2011]) 2-approximation algorithm
L. Bulteau
Pancake Flipping Is Hard
8/28
Known bounds Upper bound prd (π) ≤ 2(n − 1) Repeat at most n − 1 times
Find the largest unsorted pancake, flip it to the top Flip it back to its destination
At most 2(n − 1) flips to sort a stack.
L. Bulteau
Pancake Flipping Is Hard
9/28
Known bounds Upper bound prd (π) ≤ 2(n − 1) Anything better ?
L. Bulteau
Pancake Flipping Is Hard
9/28
Known bounds Upper bound prd (π) ≤ 2(n − 1) Anything better ? – Yes : prd (π) ≤ (5n + 5)/3 [Gates & Papadimitriou, 1979]
L. Bulteau
Pancake Flipping Is Hard
9/28
Known bounds Upper bound prd (π) ≤ 2(n − 1) Anything better ? – Yes : prd (π) ≤ (5n + 5)/3 [Gates & Papadimitriou, 1979] prd (π) ≤ (18n)/11 + O(1) [Chitturi et al., 2009]
L. Bulteau
Pancake Flipping Is Hard
9/28
Known bounds Upper bound prd (π) ≤ (18n)/11 + O(1) [Chitturi et al., 2009]
Lower bound prd (π) ≥ db (π) Breakpoint at position i if: i < n and π(i + 1) 6= π(i) ± 1 i = n and π(n) 6= n
db (π) : number of breakpoints
L. Bulteau
Pancake Flipping Is Hard
9/28
Known bounds Upper bound prd (π) ≤ (18n)/11 + O(1) [Chitturi et al., 2009]
Lower bound prd (π) ≥ db (π) Breakpoint at position i if: i < n and π(i + 1) 6= π(i) ± 1 i = n and π(n) 6= n
db (π) : number of breakpoints
At most one breakpoint is removed with each flip
L. Bulteau
Pancake Flipping Is Hard
9/28
Our result
Reduction from 3-SAT: from a formula φ, create a permutation πφ such that prd (πφ ) = db (πφ ) iff φ is satisfiable. Given a permutation π, deciding wether π can be sorted with no more than db (π) flips is NP-hard. MIN-SBPR is NP-hard (hence NP-complete)
L. Bulteau
Pancake Flipping Is Hard
10/28
Reduction
L. Bulteau
Pancake Flipping Is Hard
11/28
Efficient flips A flip is efficient if it removes one breakpoint: π → π0 prd (πφ ) = db (πφ ) iff there exists a “path” of efficient flips from πφ to the Identity. πφ →∗ In1 At most two efficient flips are possible from every permutation
h .. . x h−1 .. . y h+1 .. . L. Bulteau
Pancake Flipping Is Hard
12/28
Efficient flips A flip is efficient if it removes one breakpoint: π → π0 prd (πφ ) = db (πφ ) iff there exists a “path” of efficient flips from πφ to the Identity. πφ →∗ In1 At most two efficient flips are possible from every permutation
x .. .
h .. .
y .. .
x h h−1 h−1 & x .. h−1 . . .. .. . y . y h+1 h .. h+1 h + 1 . .. .. . . L. Bulteau
Pancake Flipping Is Hard
12/28
Efficient flips A flip is efficient if it removes one breakpoint: π → π0 prd (πφ ) = db (πφ ) iff there exists a “path” of efficient flips from πφ to the Identity. πφ →∗ In1 At most two efficient flips are possible from every permutation
x .. . h X h−1 . .. . y h+1 .. . L. Bulteau
Pancake Flipping Is Hard
h .. .
y .. .
x =h−2 h−1 h−1 & x .. . .. y . h+1 .. .
h h+1 .. . 12/28
Efficient flips A flip is efficient if it removes one breakpoint: π → π0 prd (πφ ) = db (πφ ) iff there exists a “path” of efficient flips from πφ to the Identity. πφ →∗ In1 At most two efficient flips are possible from every permutation
x .. .
h .. .
y .. .
x h h−1 h−1 & X .. h−1 . x . .. .. . y =h+2 . y h+1 h .. h+1 h + 1 . .. .. . . L. Bulteau
Pancake Flipping Is Hard
12/28
Efficient flips A flip is efficient if it removes one breakpoint: π → π0 prd (πφ ) = db (πφ ) iff there exists a “path” of efficient flips from πφ to the Identity. πφ →∗ In1 At most two efficient flips are possible from every permutation
x .. .
x h X h−1 . .. . y y h+1 .. . L. Bulteau
Pancake Flipping Is Hard
h .. .
y .. .
=h−2 h−1 h−1 & X .. x . .. =h+2 . h+1 .. .
h h+1 .. . 12/28
Reduction ideas
Create πφ in order to know precisely which efficient flips are possible (from πφ or subsequent permutations) One possible flip: usual case, there is one path to follow Two possible flips: a choice has to be made e.g., assigning “true” or “false” to a variable No possible flip: bad choices have been made e.g., a clause is unsatisfied Necessity to end with the Identity permutation.
L. Bulteau
Pancake Flipping Is Hard
13/28
Gadgets Lock 3 states: closed, open, tested
πφ Literals Lock
Variable Fork
Clause Hook
Integers
L. Bulteau
Pancake Flipping Is Hard
14/28
Dock
Gadgets Lock 3 states: closed, open, tested Fork chooses between two options
πφ Literals Lock
Variable Fork
Clause Hook
Integers
L. Bulteau
Pancake Flipping Is Hard
14/28
Dock
Gadgets Lock 3 states: closed, open, tested Fork chooses between two options Hook moves a subsequence in/out of the head
πφ Literals Lock
Variable Fork
Clause Hook
Integers
L. Bulteau
Pancake Flipping Is Hard
14/28
Dock
Gadgets Lock 3 states: closed, open, tested Fork chooses between two options Hook moves a subsequence in/out of the head Dock stores subsequences when they are sorted πφ Literals Lock
Variable Fork
Clause Hook
Integers
L. Bulteau
Pancake Flipping Is Hard
14/28
Dock
Gadgets Lock 3 states: closed, open, tested
Literals holds a lock for each literal in the formula
Fork chooses between two options Hook moves a subsequence in/out of the head Dock stores subsequences when they are sorted πφ Literals Lock
Variable Fork
Clause Hook
Integers
L. Bulteau
Pancake Flipping Is Hard
14/28
Dock
Gadgets Lock 3 states: closed, open, tested
Literals holds a lock for each literal in the formula
Fork chooses between two options
Hook moves a subsequence in/out of Variable opens locks corresponding the head to either x or ¬x Dock stores subsequences when they are sorted πφ Literals Lock
Variable Fork
Clause Hook
Integers
L. Bulteau
Pancake Flipping Is Hard
14/28
Dock
Gadgets Lock 3 states: closed, open, tested
Literals holds a lock for each literal in the formula
Fork chooses between two options
Hook moves a subsequence in/out of Variable opens locks corresponding the head to either x or ¬x Dock stores subsequences when they Clause tests one lock out of three are sorted πφ Literals Lock
Variable Fork
Clause Hook
Integers
L. Bulteau
Pancake Flipping Is Hard
14/28
Dock
Lock gadget Lock gadget (closed) 1 2 9 8 5 L= 6 4 3 11 12 key = 10 test = 7 L. Bulteau
Pancake Flipping Is Hard
15/28
Lock gadget Lock gadget (closed)
Open
1 2 9 8 5 L= 6 4 3 11 12
1 2 3 4 6 Lo = 5 8 9 10 11 12
key = 10 test = 7 L. Bulteau
Pancake Flipping Is Hard
15/28
Lock gadget Lock gadget (closed)
Open
1 2 9 8 5 L= 6 4 3 11 12
1 2 3 4 6 Lo = 5 8 9 10 11 12
Tested
1 I12
key = 10 test = 7 L. Bulteau
Pancake Flipping Is Hard
15/28
1 2 3 4 5 6 = 7 8 9 10 11 12
Lock gadget Lock gadget (closed)
Open
p+1 p+2 p+9 p+8 p+5 L= p+6 p+4 p+3 p + 11 p + 12
p+1 p+2 p+3 p+4 p+6 Lo = p + 5 p+8 p+9 p + 10 p + 11 p + 12
Tested
key = p + 10 test = p + 7 L. Bulteau
Pancake Flipping Is Hard
15/28
p+1 Ip+12
p+1 p+2 p+3 p+4 p+5 p+6 = p+7 p+8 p+9 p + 10 p + 11 p + 12
Lock gadget Lock gadget (closed)
Open
1 2 9 8 5 L= 6 4 3 11 12
1 2 3 4 6 Lo = 5 8 9 10 11 12
Tested
1 I12
key = 10 test = 7 L. Bulteau
Pancake Flipping Is Hard
15/28
1 2 3 4 5 6 = 7 8 9 10 11 12
Lock gadget
Opening
Testing (when open)
Testing (when closed)
L. Bulteau
Pancake Flipping Is Hard
key .. . L .. . test .. . Lo .. . test .. . L .. .
→∗
.. . Lo .. . .. .
→∗
→∗ ∅
16/28
1 I12 .. .
Lock gadget key Opening
X L
→∗
X Lo Y
Y test Testing (when open)
X Lo
→∗
Y
Y test Testing (when closed)
X L
→∗ ∅
Y L. Bulteau
Pancake Flipping Is Hard
X 1 I12
16/28
Lock gadget key X L Y
L. Bulteau
10 X 1 2 9 8 5 6 4 3 11 12 Y
Pancake Flipping Is Hard
17/28
Lock gadget key X L Y
L. Bulteau
2 1 ?X 10 9 8 5 6 4 3 11 12 Y
10 X 3 1 4 2 6 9 5 8 8 . 5 & 9 6 2 4 1 3 ?X 11 10 12 11 Y 12 Y
Pancake Flipping Is Hard
17/28
Lock gadget key X L Y
L. Bulteau
2 1 ?X 10 9 8 . 5 6 ∅ 4 3 11 12 Y
10 X 3 1 4 2 6 9 5 8 8 . 5 & 9 6 2 4 1 3 ?X 11 10 12 11 Y 12 Y
Pancake Flipping Is Hard
17/28
Lock gadget key X L Y
L. Bulteau
2 1 ?X 10 9 8 . 5 6 ∅ 4 3 11 12 Y
10 X 3 1 4 2 9 6 9 8 5 8 5 8 6 . 5 & 9 6 4 2 & 4 3 1 3 2 ?X 11 1 10 ? 12 X 11 Y 10 12 11 Y 12 Y
Pancake Flipping Is Hard
17/28
Lock gadget key X L Y
L. Bulteau
2 1 ?X 10 9 8 . 5 6 ∅ 4 3 11 12 Y
10 X 3 1 4 2 9 6 9 8 5 X 8 5 8 1 6 . 5 & 9 2 6 4 2 & 3 4 3 1 4 3 2 & ?X 6 X 11 1 o 10 5 L = ?X 12 11 8 Y Y 10 12 9 11 Y 10 12 11 Y 12 Y
Pancake Flipping Is Hard
17/28
Lock gadget test X L Y
L. Bulteau
7 X 1 2 9 8 5 →∅ 6 4 3 11 12 Y
Pancake Flipping Is Hard
18/28
Lock gadget test X Lo Y
L. Bulteau
7 4 X 5 3 1 6 6 2 2 4 5 X 3 4 1 1 3 ?X 2 4 2 3 7 6 1 2 3 . &? 6 5 X 1 4 . &? 5 8 7 X 5 ∅ X & 9 8 7 6 8 1 = I12 8 7 9 10 9 Y 10 11 10 9 8 11 12 11 10 9 12 Y 12 11 10 Y Y 12 11 Y 12 Y Pancake Flipping Is Hard
19/28
Overall flow Literals xi : set Pi ¬xi : set Ni
Open locks in P1
aj ∨ bj ∨ cj
L. Bulteau
Open remaining locks in P1 ∪ N1
.. .
.. .
Open locks in Nl
Open remaining locks in Pl ∪ Nl
.. .
.. .
Clause Cj
Open locks in N1
Open locks in Pl
Test lock a1
Test lock b1
Test lock c1
Test remaining locks in {a1 , b1 , c1 }
.. .
.. .
.. .
.. .
Test lock ak
Test lock bk
Test lock ck
Test remaining locks in {ak , bk , ck }
Pancake Flipping Is Hard
20/28
I
Fork gadget 11 8 E= 7 3 10 9 6 12 13 F = 4 5 15 14 2 1 L. Bulteau
Pancake Flipping Is Hard
21/28
Fork gadget 11 8 E= 7 3 10 9 6 12 13 F = 4 5 15 14 2 1 L. Bulteau
10 3 9 7 6 8 7 11 8 10 11 9 12 6 2 1 F = 13 F = 12 14 13 15 4 5 5 4 15 3 14 2 2 1 1 Pancake Flipping Is Hard
21/28
Fork gadget 11 8 E= 7 3 10 9 6 12 13 F = 4 5 15 14 2 1 L. Bulteau
. . F 1 = .. F 2 = ..
Pancake Flipping Is Hard
21/28
Fork gadget Two efficient paths
11 8 E= 7 3 10 9 6 12 13 F = 4 5 15 14 2 1 L. Bulteau
. . F 1 = .. F 2 = ..
E X ? X ∗. &∗ X F F1 F2 .. .. .. . . . ?I 1 F1 15 ∗ .. → .. . . ?I 1 F2 15 ∗ → .. .. . .
Pancake Flipping Is Hard
21/28
Hook gadget G=
3 4
12 11 6 5 H= 9 8 2 1 take = 10 put = 7 L. Bulteau
Pancake Flipping Is Hard
22/28
Hook gadget G=
3 4
. G 0 = .. . H 0 = ..
12 11 6 5 H= 9 8 2 1
. G 00 = .. . H 00 = ..
take = 10 put = 7 L. Bulteau
Pancake Flipping Is Hard
22/28
Hook gadget G=
3 4
. G 0 = ..
Moves a substring up and down
. H 0 = .. 12 11 6 5 H= 9 8 2 1
. G 00 = .. . H 00 = ..
G X H .. .
→∗
X G0 .. . H0 .. .
put .. . X0 00 0 G G ∗ .. → X 0 . H 00 H0 .. .. . .
G 00 X X ∗ ?I 1 12 H 00 → .. .. . .
take = 10 put = 7 L. Bulteau
take .. .
Pancake Flipping Is Hard
22/28
Dock gadget
1 2 Dock(2, 7) = 8 9
L. Bulteau
Pancake Flipping Is Hard
23/28
Dock gadget
1 2 Dock(2, 7) = 8 9
L. Bulteau
Stores a sorted substring (?I) out of the head of the stack.
Pancake Flipping Is Hard
?I 3
7 .. .. . . →∗ I91 Dock(2, 7) .. .. . .
23/28
Variable gadget take
Variable gadget
.. .
1 First part Move up the main sequence
G E keyp1 .. . keypq put keyn1 .. . keynq′ F H .. . Dock L. Bulteau
Pancake Flipping Is Hard
24/28
Fork
Hook
Variable gadget E keyp1 .. .
Variable gadget 1 First part Move up the main sequence 2 Choose between xi and ¬xi
Fork
keypq put keyn1 .. . keynq′ F G′ .. . H′ .. . Dock
L. Bulteau
Pancake Flipping Is Hard
24/28
Hook
Variable gadget Variable gadget 1 First part Move up the main sequence 2 Choose between xi and ¬xi 3 Open locks in Ni
keynq′ .. . keyn1 put keypq .. . keyp1 F2 G′ .. . H′ .. . Dock
L. Bulteau
Pancake Flipping Is Hard
24/28
Hook
Variable gadget put keyn1 .. .
Variable gadget 1 First part Move up the main sequence 2 Choose between xi and ¬xi 3 Open locks in Ni
4 Put back main sequence
keynq′ F2 G′ .. . H′ .. . Dock
L. Bulteau
Pancake Flipping Is Hard
24/28
Hook
Variable gadget Variable gadget
.. .
1 First part Move up the main sequence 2 Choose between xi and ¬xi
G ′′ keyn1 .. .
3 Open locks in Ni
4 Put back main sequence 5 Other gadgets are activated
keynq′ F2 H ′′ .. . Dock
L. Bulteau
Pancake Flipping Is Hard
24/28
Hook
Variable gadget Variable gadget
G ′′ keyn1 .. .
1 First part Move up the main sequence 2 Choose between xi and ¬xi 3 Open locks in Ni
4 Put back main sequence 5 Other gadgets are activated 6 Second part Hook collapses
L. Bulteau
Pancake Flipping Is Hard
keynq′ F2 H ′′ .. . Dock
24/28
Hook
Variable gadget Variable gadget
keyn1 .. .
1 First part Move up the main sequence 2 Choose between xi and ¬xi 3 Open locks in Ni
4 Put back main sequence 5 Other gadgets are activated
keynq′ F2 ⋆I .. . Dock
6 Second part Hook collapses 7 Open locks in Pi
L. Bulteau
Pancake Flipping Is Hard
24/28
Variable gadget Variable gadget
F2 ⋆ I .. .
1 First part Move up the main sequence 2 Choose between xi and ¬xi 3 Open locks in Ni
Dock
4 Put back main sequence 5 Other gadgets are activated 6 Second part Hook collapses 7 Open locks in Pi 8 Fork collapses
L. Bulteau
Pancake Flipping Is Hard
24/28
Variable gadget Variable gadget 1 First part Move up the main sequence 2 Choose between xi and ¬xi 3 Open locks in Ni
⋆ I ⋆
I .. . Dock
4 Put back main sequence 5 Other gadgets are activated 6 Second part Hook collapses 7 Open locks in Pi 8 Fork collapses 9 Dock stores sorted sequences
L. Bulteau
Pancake Flipping Is Hard
24/28
Variable gadget Variable gadget 1 First part Move up the main sequence 2 Choose between xi and ¬xi
.. . I
3 Open locks in Ni
4 Put back main sequence 5 Other gadgets are activated 6 Second part Hook collapses 7 Open locks in Pi 8 Fork collapses 9 Dock stores sorted sequences 10 End Gadget sorted
L. Bulteau
Pancake Flipping Is Hard
24/28
Clause gadget take1 .. .
Same structure, with two choices: [[a or b] or c]
Hook 2
L. Bulteau
Pancake Flipping Is Hard
Fork 2
G1 E1 take2 put1 testc F1 G2 E2 testa put2 testb F2 H2 H1 .. . Dock1 Dock2 25/28
Fork 1
Hook 1
Overall construction takeV1 .. .
Open locks in P1
takeVl takeC1 .. . takeCk V1 πφ = .. . Vl C1 .. . Ck (docks) (locks) L. Bulteau
Open locks in N1
Open remaining locks in P1 ∪ N1
.. .
.. .
Open locks in Nl
Open remaining locks in Pl ∪ Nl
.. .
.. .
Open locks in Pl
Test lock a1
Test lock b1
Test lock c1
Test remaining locks in {a1 , b1 , c1 }
.. .
.. .
.. .
.. .
Test lock ak
Test lock bk
Test lock ck
Test remaining locks in {ak , bk , ck }
Pancake Flipping Is Hard
26/28
I
Finally
There exists an efficient path from πφ to the identity iff φ is satisfiable. The construction requires a polynomial time. MIN-SBPR is NP-hard.
L. Bulteau
Pancake Flipping Is Hard
27/28
Conclusion
The complexity class of the Pancake Flipping problem is settled There remains many intriguing questions: What about the burnt variant? Any approximation algorithm? Any FPT algorithm with a relevant parameter? Any better bound for the diameter than 1.07n ≤ f (n) ≤ 1.64n (unburnt) and 1.5n ≤ g (n) ≤ 2n (burnt)?
L. Bulteau
Pancake Flipping Is Hard
28/28
Conclusion
The complexity class of the Pancake Flipping problem is settled There remains many intriguing questions: What about the burnt variant? Any approximation algorithm? Any FPT algorithm with a relevant parameter? Any better bound for the diameter than 1.07n ≤ f (n) ≤ 1.64n (unburnt) and 1.5n ≤ g (n) ≤ 2n (burnt)?
Thank you!
L. Bulteau
Pancake Flipping Is Hard
28/28