Pancake Flipping Is Hard

9 downloads 203 Views 894KB Size Report
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