В ответе на предыдущий вопрос я упомянул распространенное, но ошибочное мнение, что «гауссовское» исключение происходит за времени. Хотя очевидно, что алгоритм использует O ( n 3 ) арифметических операций, небрежная реализация может создавать числа с экспоненциально большим количеством битов. В...
Я практикующий программист, и я пишу обзор алгебраических структур для личного исследования и пытаюсь привести примеры того, как эти структуры используются в теоретической информатике (и, в меньшей степени, в других областях компьютерных наук). , В рамках теории групп я встречал синтаксические...
Широко распространено мнение, что , оптимальный показатель для умножения матриц, фактически равен 2. Мой вопрос прост:ωω\omega Какие у нас есть основания полагать, что ?ω=2ω=2\omega = 2 Мне известны быстрые алгоритмы, такие как Coppersmith-Winograd, но я не знаю, почему их можно считать...
Мой вопрос прост: Что наихудшее время работы наилучшего известного алгоритма для вычисления eigendecomposition в качестве матрицы?n×nn×nn \times n Собственное разложение сводится к умножению матриц или в худшем случае наиболее известные алгоритмы (через SVD )?O(n3)O(n3)O(n^3) Обратите внимание, что...
Принято считать, что для всех ε > 0ε>0\epsilon > 0 можно умножить две матрицы n × nN×Nn \times n за O ( n2 + ϵ)О(N2+ε)O(n^{2 + \epsilon}) времени. Некоторое обсуждение здесь . Я спросил некоторых людей, которые более знакомы с исследованием, думают ли они, что существует k > 0К>0k>0...
У меня очень сильная база в алгебре, а именно коммутативная алгебра, гомологическая алгебра, теория поля, теория категорий, и я в настоящее время изучаю алгебраическую геометрию. Я - математик со склонностью переключаться на теоретическую информатику. Помня вышеупомянутые области, какое поле было...
Я хотел бы найти алгоритм полиномиального времени, который определяет, содержит ли диапазон данного набора матриц матрицу перестановок. Если кто-нибудь знает, относится ли эта проблема к другому классу сложности, это было бы так же полезно. РЕДАКТИРОВАТЬ: я пометил этот вопрос с помощью линейного...
Мне известны только два доказательства леммы Шварца – Циппеля. Первое (более распространенное) доказательство описано в записи википедии . Второе доказательство открыл Дана Мошковиц. Есть ли другие доказательства, которые используют существенно разные идеи?...
Даны mmm от nnn двоичной матрицы MMM (записи являются 000 или 111 ), проблема в том , чтобы определить, существует два двоичных векторов v1≠v2v1≠v2v_1 \ne v_2 таким образом, что Mv1=Mv2Mv1=Mv2Mv_1 = Mv_2 (все операции , выполняемые над ZZ\mathbb{Z} ). Эта проблема NP-сложная? Это ясно в NP,...
Недавно я читал «Две дуальности вычислений: отрицательные и дробные типы» . В статье рассматриваются типы сумм и типы товаров, в которых даны семантика для типов a - bи a/b. В отличие от сложения и умножения, существует не одна, а две инверсии возведения в степень, логарифмы и корни. Если типы...
Пусть - квадратная целочисленная матрица, а n - положительное целое число. Меня интересует сложность решения следующей проблемы:MMMnnn Является ли запись в верхнем правом углу положительной?MnMnM^n Обратите внимание, что очевидный подход повторного возведения в квадрат (или любого другого явного...
Я ищу хороший обзор алгоритмов и сложности линейной алгебры (операции типа ранга, обратные, собственные значения, ... для логических, и целых / рациональных матриц) с акцентом на параллельные ( иерархия N C ) и полимерные алгоритмы , Я не мог найти недавний.FpFp\mathbb{F}_pNCNCNC Знаете ли вы...
Отказ от ответственности: я не теоретик CS. Исходя из абстрактной алгебры, я привык иметь дело с вещами, равными изоморфизму, - но у меня возникли проблемы с переводом этого понятия в структуры данных. Сначала я подумал, что достаточно точных теоретических биективных морфизмов, но я довольно быстро...
Кто-нибудь может мне помочь со следующей проблемой? Я хочу найти некоторые значения a i , b jai,bja_i,b_j (mod NNN ), где i = 1 , 2 , … , K , j = 1 , 2 , … , Ki=1,2,…,K,j=1,2,…,Ki=1,2,…,K, j=1,2,…,K (например, К = 6K=6K=6 ), учитывая список значений К 2K2K^2 которые соответствуют различиям a i - b...
Основное свойство векторных пространств состоит в том, что векторное пространство размерности может характеризоваться линейно независимыми линейными ограничениями, то есть существуют линейно независимых векторов , ортогональных .В⊆ FN2В⊆F2NV \subseteq \mathbb{F}_2^nн - дN-dn-dddddddвес1, … , Шd∈...
Rn\mathbb{R}^n⟨⋅,⋅⟩\langle \cdot, \cdot \ranglemmv1,v2,…,vmv_1, v_2, \ldots, v_mx∈Rnx \in \mathbb{R}^nмин я ⟨ х , v я ⟩ mini⟨x,vi⟩\min_i \langle x, v_i \rangleО ( п т )O(nm)O(nm) п = 2 n=2n = 2O ( войти 2 м )O(log2m)O(\log^2 m) Единственное, что я могу придумать, это следующее. Непосредственным...
Я ищу обзорную статью или книгу, в которой освещаются результаты о пространственной сложности общих операций линейной алгебры, таких как ранг матрицы, вычисление собственных значений и т. Д. Я подчеркиваю часть «пространственная сложность», означающую сложность рабочего пространства, а не временную...
Меня интересует следующая задача: заданы целочисленные матрицы A1,A2,…,AkA1,A2,…,AkA_1,A_2, \ldots, A_k решают, равно ли каждое бесконечное произведение этих матриц нулевой матрице. Это означает именно то, что вы думаете, что он делает: мы будем говорить, что множество матриц обладает тем...
Меня интересует сложность решения линейных уравнений по модулю k для произвольного k (и с особым интересом к простым степеням), а именно: Проблема. Для данной системы из линейных уравнений по неизвестным по модулю , существуют ли какие-либо решения?н кmmmnnnkkk В аннотации к своей статье Структура...
У меня есть достаточное образование по математике, но я никогда не чувствовал себя уверенно на 100% с абстрактной алгеброй (математика групп, колец, полей и т. Д.). Я думаю, что это было отчасти потому, что мне нужно было увидеть приложения, и все, что я мог найти, были в физике, а не в CS....