Мне кажется (более того, я уверен), что приведенный алгоритм все-таки решает задачу за полиномиальное время всегда! Правда, используя для этого слишком много пространства…

Кстати, да! Хотя от генетики здесь маловато чего есть, но ее применение в данном контексте напрашивается :)

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

Ну, я же честно сказал, что полиномиальным является только время! :) Кстати, я совсем не уверен, что какая-нибудь модификация МТ (со сколь угодно большим числом головок) сможет решить данную задачу за полиномиальное время, по крайней мере, если начальные данные записаны только на одной ее ленте…

Да, как раз с биологического «железа» все и началось, Адлеман (Adleman, кстати, тот самый, чья буковка A стоит в аббревиатуре RSA) в начале 1990-х собственоручно провел опыт по решению задачи HPP с помощью ДНК-молекул для графа с 6 вершинами. Потратив на это несколько дней. :) Ссылка в начале топика есть. Если публике будет интересно, то я мог бы про это написать…

Очень хотелось бы послушать про реализацию (в том числе и про распараллеливание) циклов в потоковых системах…

У меня получилась 41 команда. Последовательность действий такая: 1) переводим числитель в десятичную с/с; 2) приписываем к нему справа 4 нуля; 3) переводим его обратно в унарную с/с; 4) выполняем целочисленое деление в унарной с/с; 5) переводим результат в десятичную с/с (с правильной установкой точки). Шаги 1 и 5 выполняются одними и теми же командами. Сам алгоритм:

/ :: AB
|A :: A|
A :: X
0| :: 1
1| :: 2
.....
8| :: 9
9| :: |0
.| :: |.
X| :: X1
B :: 0000CD
1* :: 0
2* :: 1
.....
9* :: 8
0* :: *9
X0 :: X
XC :: [empty]
C :: *C| 
+P :: |+
P| :: |P
|D| :: DP
DP :: D|+
D| :: Z
Z| :: Z
ZP :: Z
Z+ :: X0.0000|Q
Q+ :: |Q
Q :: [empty]
X. :: 0. [FIN]
X :: [empty] [FIN] 

Выполняется, правда, подольше, но автором задача наискорейшего выполнения и не ставилась :)

Хм, насколько я понимаю, определяющее свойство пирамиды — ключ любого узла не меньше любого ключа в соответствующем поддереве (с корнем в данном узле). Если я хочу найти некоторый элемент в пирамиде, то я начинаю с корня (точка доступа к пирамиде). Если искомый элемент больше ключа в корне, то сразу ясно, что такого ключа в пирамиде нет, ибо корень хранит наибольший ключ. Если ключи совпадают, то мы нашли то, что искали, правда, если цель — найти все такие ключи, то придется поиск продолжить. И тут мы плавно переходим к третьей альтернативе — искомый ключ меньше корневого. Значит его надо искать либо в правом поддереве, либо в левом. Но в каком конкретно? А этого то мы и не знаем — значит придется искать и там, и там. Т.е. никакого разделения задачи на две подзадачи с последующим отбрасыванием одной из них (двоичный поиск) не получается. Получается, что сравнением заданного ключа с корнем мы добились только отбрасывания одного единственного ключа из всего дерева — поэтому-то в худшем случае поиск и будет требовать O(n) действий. Как-то так…

На вставку одного элемента тратится не более 2n^1/2 действий. На вставку n элементов — не более 2n^3/2 действий. После того, как таблица построена, из нее извлекаются по очереди все элементы, на извлечение одного элемента тратим не более 2n^1/2 шагов, на извлечение всех элементов — 2n^3/2 шагов. Т.к. эти два процесса (создание таблицы и ее уничтожение) происходят последовательно, то общая сложность не превышает суммы сложностей отдельных шагов, т.е. 4n^3/2 или O(n^3/2)…

Кстати, да — хорошее название, спасибо!

Уже исправил, спасибо!