Подборка arXiv · 16.11.20261. Случайная поправка не всегда упрощает задачуМожно ли быстрее решать линейные уравнения, где неизвестные лишь умножают на заданные числа и складывают? Авторы допускают небольшие изменения этих чисел. Стоимость они измеряют числом операций, вычисляющих левые части уравнений по пробным значениям неизвестных. По их результату, подстройка поправок под задачу может дать большой выигрыш по сравнению со случайными поправками. Но для такого выигрыша на любых системах сам алгоритм должен использовать случайность.
Для приближённых вычислений важно не только насколько мало изменились условия, но и подстроены ли изменения под конкретную задачу.
2. Как получить повторный корень из простых слагаемыхКакая самая высокая степень нужна в многочлене, составленном из разных степеней неизвестной и единицы со знаками плюс или минус? Авторы требуют, чтобы он делился на квадрат или куб одного заданного многочлена. У того есть корень больше единицы, то есть значение, при котором он равен нулю. Повтор множителя обеспечивает повтор корня. Для обоих требований авторы определяют наименьшую возможную высшую степень. Вывод относится именно к выбранному множителю.
Такие выражения уже находили раньше. Новизна в точной границе, ниже которой обойтись меньшими степенями неизвестной невозможно.
3. Насколько оценка сложности узла может промахнутьсяСколько локальных перестроек нужно, чтобы превратить замкнутый узел в простое кольцо? Авторы фиксируют одно правило перестройки и сравнивают минимум шагов с известной нижней оценкой, которая гарантирует лишь, что шагов будет не меньше. Они различают ходы, повышающие и понижающие числовую характеристику узла, на которой основана оценка. Для выбранного семейства узлов авторы показывают, что оценка может недосчитывать сколь угодно много шагов.
Разрыв нельзя перекрыть, добавив к оценке один фиксированный запас шагов для всех узлов. Верная оценка может быть очень далека от точной.
Следить за своими темами, авторами и разделами можно в бесплатном
arXiv-боте. Для доступа достаточно подписаться на канал «Математика не для всех».
Читайте «Математика не для всех» в
MAX,
Дзене и
ВКонтакте.
#Математика #arXiv #Исследования