Блины переворачивать сложно — NP сложно

Французские компьютерщики наконец-то доказали, что сортировка блинов — сложная задача.

Нет, правда — это не шутка. Что ж, это немного забавно, но это только потому, что это преподносится как переворачивание блинов. Рассматриваемый алгоритм сортирует перестановку с использованием обращения префикса, что намного проще понять в терминах блинов.

Переворачивание блинов — давняя алгоритмическая проблема.

Вы начинаете со стопки блинов разного размера, и ваша задача — рассортировать их по порядку. Единственное ограничение, которое усложняет задачу, заключается в том, что их нельзя трогать ничем, кроме лопатки. Все, что вы можете сделать, это вставить лопатку в точку разделения и перевернуть весь набор блинов, который вы подняли, вверх ногами за одну операцию.

Есть вариант задачи, когда вы сожгли все блины с одной стороны, и вам нужно закончить сортировку всеми сожженными сторонами вниз.

В обоих случаях необходимо ответить на вопрос: если в стеке n блинов, какое максимальное количество флипов необходимо в зависимости от n, то есть f (n)?

Короче, какова вычислительная сложность задачи о блине?

На данный момент мы знаем только f (n) для n <= 19 (для выжженной версии задачи мы знаем это только для n <= 17). Помимо этого, мы знаем несколько общих верхних и нижних границ, но они не считаются особенно жесткими. Теперь команде из трех ученых-информатиков из Лаборатории информатики в Атлантическом Нант-Атланте удалось доказать, что проблема блинчиков является сложной задачей. Грубо говоря, это делает задачу по крайней мере такой же сложной, как самая сложная в классе NP. Это означает, что если вы можете найти решение задачи с блинами за полиномиальное время, то вы доказали, что P = NP. В статье не улучшаются оценки функции сложности, но удалось показать, что доказательство того, что известная нижняя граница - количество точек останова - является точной нижней границей, также является NP трудным. Алгоритм действительно имеет некоторые практические цели - например, в сравнительной геномике, и есть еще более полезная связанная проблема сортировки путем обращения. Но кому нужны практические приложения, чтобы интересоваться блинами?