Обсуждение:Тест Агравала — Каяла — Саксены

(untitled)

• Почему алгоритм называется полиноминальным, если он логарифмический(что следует из оценки сложности) ? Это имхо не отражает сути. Разве остальные известные алгоритмы не полиноминальные? Например, перебор всех чисел от 2 до n. 79.164.171.29 23:57, 7 июля 2009 (UTC)alex
  • В теории сложности и теории оптимизации обычно рассматривают сложность алгоритма от длины входа. Если кодировать вход числом палочек (унарная система счисления), то длина входа будет совпадать с самим числом, однако эта кодировка будет избыточной. Если же представлять число в позиционной системе счисления (скажем, двоичной или десятичной), то длина входа будет выражаться, очевидно, логарифмом числа. Так вот, тест АКС - первый алгоритм, полиномиальный относительно длины входа (перебор будет экспоненциальным по длине входа). Overrider 07:05, 14 июля 2009 (UTC)

Ссылка устарела.

Единственная ссылка более не указует на документ. В рунете описания этого алгоритма не нашел. --94.25.153.121 20:26, 25 июня 2010 (UTC)

• Ссылку обновил. Maxal 20:28, 25 июня 2010 (UTC)

Сверка

Выбрал (методом случайной статьи) данную статью для тестирования процесса сверки. Здесь буду кратко записывать замечания по ходу предварительной работы.

• Статья тяжеловата даже для имеющего математическую подготовку. В частности, пришлось добавить, что такое Fp и как понимать x = y mod (a, b) — это очевидно, по всей вероятности, только тем, кто вплотную занимается теорией чисел, криптографией и т. п. Также несколько смущает log²x, так как не сразу очевидно, является ли это аналогом sin²x.
• Очень много математических выкладок. В частности, лемм, тогда как теорема отсутствует. В источнике (Бараш) говорится, что алгоритм следует из теоремы, а теорема приведена. Несколько сомневаюсь, нужно ли столько деталей в викистатье, когда в то же самое время отсутствует более развёрнутое словесное описание алгоритма и его вариантов.
• В общем и целом статья кажется пригодной для сверки, если несколько сократить мат. выкладки РоманСузи 16:25, 11 октября 2014 (UTC)

• Дополнил Ссылки тремя источниками, которые могут помочь разобраться с алгоритмом, так как содержат более простые описания. (после проведения сверки неиспользованные источники можно сократить) РоманСузи 14:19, 18 октября 2014 (UTC)

• Дополнил и проверил основную идею, алгоритм и вторгся в обоснование. К сожалению, в обосновании много пропусков, без которых оно вообще теряет смысл. В частности, не описана группа ${\mathcal {G}}$. Все это, по-видимому, было взято из оригинальной статьи AKS. Возможно, более поздние источники внесли ясность. Также не нашел перевода на русский "introspective polinomial", "introspective numbers" - по сути это не мешает (так как есть определение), но было бы хорошо называть вещи правильными именами. РоманСузи 18:35, 18 октября 2014 (UTC)

• Проверил оставшиеся утверждения, проставил источники и поставил отметку на статью.

• Следующие моменты: для раздела Основные свойства не нашёл именно такого подбора примеров, но материал достаточно тривиален, чтобы редактор мог использовать эти примеры, объяснив свойства алгоритма.

• Раздел Обоснование опирается на статью AKS (v6) с некоторыми сокращениями. Конечно, если (и когда) статья будет претендовать на избранную, нужно будет разжевать всё это побольше, но сейчас с точки зрения сверки претензий нет.

РоманСузи 15:41, 25 октября 2014 (UTC)

Время работы

Судя по английской статье, время работы алгоритма везде оценивается через en:soft O, то есть, ${\tilde {O}}(\log ^{6}p)$, а не $O(\log ^{6}p)$. Это разные понятия, потому что soft O отбрасывает все логарифмы, кроме самого весомого. Если ВП:КТОТОТАМ захочет сделать статью лучше — можно разобраться в том, где стоит так поменять и сделать это. Ну или может я доберусь когда-нибудь. Удивительно, что это прошло незамеченным на КДС… ${\texttt {adamant}}$ (обс./вклад) 02:37, 22 августа 2019 (UTC)