Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями

Как упоминалось выше, комбинаторная редукция для машин с указателями, приведенная в теореме 2, является более слабой, чем редукция для пословных RAM-машин. Например, для гипотетического алгоритма сортировки с линейным временем выполнения теорема 1 предлагает очередь с приоритетами с временем обновления O(1), а теорема Theorem – с временем обновления <math>2^{O(log^* \; n)}</math>. Остается открытым вопрос о том, можно ли устранить или уменьшить этот разрыв.