Вопросы с тегом «asymptotics»

Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...

Предположим, что для каждого ϵ>0ϵ>0\epsilon > 0 существует машина Тьюринга MϵMϵM_{\epsilon} которая определяет язык LLL во времени O(na+ϵ)O(na+ϵ)O(n^{a + \epsilon}) . Существует ли единственный алгоритм, определяющий LLL во времени O(na+o(1))O(na+o(1))O(n^{a + o(1)}) ? (Здесь член...

Каковы известные пределы разрешимости сравнения скорости роста функций из ? Я здесь думаю о разрешимости таких вопросов, как «Является ли x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?» или «Является ли 2 lg ∗ x ∈ O ( lg lg x ) ?».N→NN→N\mathbb{N} \to \mathbb{N}xx∼2⌊xlg(x+2)⌋xx∼2⌊xlg⁡(x+2)⌋x^x \sim 2^{\lfloor x \lg...

Я смущен. Я хочу доказать, что это проблема сортировкиnNn по nnn матрица, т.е. строки и столбцы в порядке возрастания Ω(n2logn)Ω(n2log⁡n)\Omega(n^2\log n), Я исхожу из предположения, что это можно сделать быстрее, чемn2lognn2log⁡nn^2\log n и попытаться нарушить log(m!)log⁡(m!)\log(m!) нижняя...