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

35
Умножение n полиномов степени 1

Задача состоит в том, чтобы вычислить многочлен . Предположим, что все коэффициенты вписываются в машинное слово, т. Е. Ими можно манипулировать в единицу времени.( а1х + б1) × ⋯ × ( аNх + бN)(a1Икс+б1)×⋯×(aNИкс+бN)(a_1 x + b_1) \times \cdots \times (a_n x + b_n) Вы можете сделать раз, применяя БПФ...

29
Полиномиальный метод для результатов сложности

Полиномиальные методы , скажем, теорема о комбинаторном нульстелленсаце и Шевалле – Предупреждениее, являются мощными инструментами аддитивной комбинаторики. Представляя проблему с собственными полиномами, они могут гарантировать существование решения или количество решений полиномов. Они...

28
Альтернативные доказательства леммы Шварца – Циппеля

Мне известны только два доказательства леммы Шварца – Циппеля. Первое (более распространенное) доказательство описано в записи википедии . Второе доказательство открыл Дана Мошковиц. Есть ли другие доказательства, которые используют существенно разные идеи?...

24
Приблизительная степень

РЕДАКТИРОВАТЬ (v2): в конце добавлен раздел о том, что я знаю о проблеме. РЕДАКТИРОВАТЬ (v3): Добавлено обсуждение пороговой степени в конце. Вопрос Этот вопрос в основном справочный запрос. Я не знаю много о проблеме. Я хочу знать, была ли предыдущая работа по этой проблеме, и если да, может ли...

23
Представление ИЛИ с полиномами

Я знаю, что тривиально функция OR для переменных может быть точно представлена ​​полиномом следующим образом: , который имеет степень .х 1 , ... , х п р ( х 1 , ... , х п ) р ( х 1 , ... , х п ) = 1 - П п я = 1 ( 1 - х я ) пNnnИкс1, … , ХNx1,…,xnx_1,\ldots, x_nр ( х1, … ,...

18
Вычисление суммы разреженных полиномов в квадрате за O (n log n) времени?

Предположим , что мы имеем полиномы степени не более n , n > m , так что общее число ненулевых коэффициентов равно n (т. е. многочлены редки). Меня интересует эффективный алгоритм вычисления полинома:p1,...,pmp1,...,pmp_1,...,p_mnnnn>mn>mn>mnnn ∑ipi(x)2∑ipi(x)2\sum_i p_i(x)^2 Поскольку...

13
Каково смещение случайных многочленов с низкой степенью над GF (2)?

У меня есть вопрос, касающийся полиномов и вероятностей низкой степени: какова (асиптотическое поведение) вероятность того, что случайный * полином ppp по GF (2) со степенью и n переменных имеет .≤d≤d\le...

13
Оценивая мультилинеаризацию арифметической схемы?

Пусть быть мульти-мерный полином с коэффициентами над полем . Мультилинеаризация , обозначаемая , является результатом многократной замены каждого с на . Результат, очевидно, является полилинейным полиномом.р ( х 1 , ... , х п ) F р р х д я д > 1 х...

12
Явные полиномы от 1 переменной с нижними границами сложности суперлогарифмической схемы?

Подсчитав аргументы, можно показать, что существуют многочлены степени n от 1 переменной (т. Что-то вроде которые имеют сложность схемы n. Также можно показать, что для многочлена типа требуется как минимум умножений (это нужно просто для получения достаточно высокой степени). Существуют ли явные...

11
Существует ли P-полная задача о диофантовых уравнениях?

В целом решение о том, имеет ли диофантово уравнение какое-либо целочисленное решение, эквивалентно проблеме остановки. Я считаю, что решение о том, имеет ли какое-либо решение квадратное диофантово уравнение, является NP-полным. Существует ли дополнительное ограничение на используемые уравнения,...

10
Каковы некоторые результаты по алгоритмам, которые оценивают полиномы по заданному набору точек?

Кажется, есть много рандомизированных алгоритмов для проверки полиномиальной идентичности, проверяя, равен ли данный полином нулю. Есть ли какие-либо результаты алгоритмов, которые делают своего рода оценку полиномов по определенному набору точек? Это может быть, например, аппроксимация, для какой...

10
Сложность свертки в кольце max / plus

Мы можем сделать свертку в для полиномов плюс / умножение с FFT. Тем не менее, подход не кажется очень обобщенным для колец в целом. Был ли какой-нибудь прогресс по наивной свертке для кольца max / plus?O ( n logн )О(Nжурнал⁡N)O(n\log n)O ( n2)О(N2)O(n^2) Я должен отметить, что можно преобразовать...

10
О дерандомизированном тестировании полиномиальной идентичности

В тестировании тождества полиномов мы ищем детерминированный алгоритм, чтобы вывести равенство двух полиномов . Дерандомизация известных эффективных рандомизированных алгоритмов и создание эффективного детерминированного алгоритма является важной открытой проблемой. Есть ли полная проблема для PIT,...

10
Оценка симметрических полиномов

Пусть - симметрический многочлен , т. Е. Такой многочлен, что для всех и все перестановки . Для удобства можно предположить, что является конечным полем, чтобы избежать решения проблем с моделью вычислений.е: KN→ Кf:Kn→Kf:\mathbb{K}^n \to \mathbb{K}x ∈ K n σ ∈ S n Kе( х ) = е( σ( х )...

10
Поддержание значения многочлена над динамически обновляемым вводом

Пусть - многочлен над фиксированным конечным полем. Предположим, что нам задано значение P для некоторого вектора y ∈ { 0 , 1 } n и вектора y .п( х1, х2, … , ХN)P(x1,x2,…,xn)P(x_1, x_2, \ldots, x_n)пPPY∈ { 0 , 1 }Ny∈{0,1}ny \in \{0,1\}^nYyy Теперь мы хотим вычислить значение на вектор у ' ∈ { 0 , 1...

9
Систематические исследования суммы квадратичных полиномов в квадрате

Мне интересно, существуют ли систематические исследования сумм квадратичных форм в квадрате, похожих на квадратичные формы, что практически отражается в разложении по собственным значениям (что имеет огромное практическое значение). Пара примеров связана с важностью вопроса. Анализ основных...

9
Найти остаток от большого фиксированного полинома, разделив его на небольшой неизвестный полином

Предположим, мы работаем в конечном поле. Нам дан большой фиксированный многочлен p (x) (скажем, степени 1000) над этим полем. Этот многочлен известен заранее, и нам разрешено выполнять вычисления с использованием большого количества ресурсов на «начальной стадии». Эти результаты могут быть...

9
Рандомизированное тестирование идентичности для полиномов высокой степени?

Позволять еff быть Nnnмногочлен, заданный в виде арифметической схемы размера поли(N)(n)(n), и разреши пзнак равно2Ω(N)p=2Ω(n)p = 2^{\Omega(n)} быть простым. Можете ли вы проверить, если еff тождественно ноль ZпZp\mathbb{Z}_p, со временем поли(N)poly(n)\mbox{poly}(n) и вероятность ошибки...