Разрешаемая теория асимптотического роста

12

Каковы известные пределы разрешимости сравнения скорости роста функций из ? Я здесь думаю о разрешимости таких вопросов, как «Является ли x x2 x lg ( x + 2 ) ?» или «Является ли 2 lg xO ( lg lg x ) ?».NNxx2xlg(x+2)2lgxO(lglgx)

Если мы ограничим функции полиномами (выраженными обычным образом), то это не сложно. Смотрите также Кантор нормальная форма .

Насколько велик мы можем сделать класс функций до того, как сравнение станет неразрешимым? Можем ли мы распространить его на функции, используемые в типичном классе алгоритмов бакалавриата?

Как объясняет Джошуа Грохов в комментариях, меня действительно интересует набор выражений, а не сами функции. Так, например, меня будут интересовать процедуры принятия решений, которые могут сравнивать « » и « 2 », даже если они не могут сравнивать « ln e » и « n ( ln n ) - 1 ».12lnen(lnn)1

Возможно связанный вопрос: "Является ли теория асимптотических границ конечно аксиоматизируемой?"

jbapple
источник
2
Интересный вопрос! Я думаю, что одна часть должна быть немного изменена, хотя. Я не думаю, что вопрос должен быть в том, насколько велик класс функций, а в том, как функции выражаются . То есть, если в качестве входных данных вам даны две машины Тьюринга за полиномиальное время, указание того, какая из них имеет большее время выполнения, неразрешимо (несмотря на то, что оба имеют время выполнения полинома) ... Если эти функции вместо этого были выражены как, скажем, , явные полиномы (выписать все поли с коэффициентами), то это легко сравнить.
Джошуа Грохов
Хорошая точка зрения. Есть ли у вас какие-либо предложения о том, как это выразить?
Jbapple
1
Я предполагаю, что это зависит от того, что вас интересует. Возможно, было бы естественно попросить функции, выраженные в виде формулы, включающей различные операции, и тогда вопрос заключается в том, какие наборы операций делают его разрешимым / неразрешимым. например, ops будет включать +, времена, деление, -, n-е корни, exp, log, состав, log ^ * и т. д. (Если вы пропустите log ^ *, предыдущий список предоставит вам все элементарные функции.)
Джошуа Грохов

Ответы:

9

Rxexplog||f(x)5+f(x)=xв семье). Харди показал, что любые две такие функции можно сравнивать асимптотически. Я не уверен, если доказательства являются алгоритмическими, но это стоит проверить.

Boshernitzan расширил этот класс еще дальше, и, несомненно, есть другие работы на эту тему.

Юваль Фильмус
источник
В книге Джона Р. Шекелла «Символьная асимптотика» (раздел 5.1, стр. 91) говорится, что первый алгоритм для этой задачи был взят из работы Дана и Геринга 1986 года «Заметки об экспоненциально-логарифмических терминах» . В диссертации Доминика Грунца 1996 года «О вычислении пределов в системе символьных манипуляций» также содержится алгоритм для этой задачи и сравниваются различные методы.
Jbapple
2
Однако все они полагаются на оракула для решения проблемы нулевой эквивалентности, который в целом неразрешим.
Jbapple