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