Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Статья в сборнике "Математические вопросы кибернетики" №20, Москва, 2022
Авторы: Сайверт Х., Сергеев И.С., Юкна С.
Инверсные входы в арифметических и тропических схемах
Аннотация:
Известно, что сложность монотонных арифметических (+, ·)-схем можно понизить экспоненциально, если дополнительно разрешить использовать операцию деления «в самом конце», на выходе схемы. Естественно, возникает вопрос, можно ли добиться существенного выигрыша в сложности, если разрешается выполнять деления «в самом начале», т.е. если в качестве входов схемы помимо неотрицательных вещественных констант и переменных x1, …, xn, допускаются инверсные входы 1/x1, ..., 1/xn. Мы даем отрицательный ответ: в этом случае возможен не более чем квадратичный выигрыш. Такой же результат справедлив для тропических полуколец (min, +) и (max, +): в этих кольцах операции деления соответствует вычитание, а инверсные входы являются отрицаниями переменных, -x1, …, -xn. Вопрос о том, может ли добавление инверсных входов ускорить вычисления (min, +, max)-схемами, остается открытым.
Ключевые слова:
арифметические схемы, тропические схемы, инверсные входы, динамическое программирование
Язык публикации: русский,  страниц: 20 (с. 61-80)
Направление исследований:
Математические вопросы и теория численных методов
Полный текст на русском языке:
Экспорт ссылки на публикацию в формате:   RIS    BibTeX
Сведения об авторах:
  • Сайверт Ханнес,  ,  Франкфуртский университет им. Гёте
  • Сергеев Игорь Сергеевич,  ,  Научно-исследовательский институт 'Квант' (Москва)
  • Юкна Стасис,  ,  Вильнюсский университет