The Burnt Pancake Problem
We used the burnt pancake problem to
test the computational capability of a genetic device.
| Sorting a stack of four burnt pancakes |
|
| Pancake stacks... |  |
| ...can be represented as numerical permutations... | (-2, 4, -1, 3) (1, 2, 3, 4) |
...and as DNA. DNA sequences within a complete coding region have a specific order and orientation. |
 |
The Mathematical Challenge
For any given scrambeled stack what is the minimum number of flips required to solve the puzzle?
Total permutations for n pancakes:
2^n (n!)
| Graphs where stacks are represented by vertices and flips are edges | |
|
|
| n = 2 2^n (n!) = 8 permutations |
n = 3 2^n (n!) = 48 permutations |
Classical computational approaches are limited by the size of n.
Can the parallel processing power of DNA overcome this limitation?
