Меня интересует следующая задача: заданы целочисленные матрицы A1,A2,…,AkA1,A2,…,AkA_1,A_2, \ldots, A_k решают, равно ли каждое бесконечное произведение этих матриц нулевой матрице. Это означает именно то, что вы думаете, что он делает: мы будем говорить, что множество матриц обладает тем...
В 1979 году Фрейвалдс показал, что верификация матричных произведений по любому полю может быть выполнена за рандомизированное время . Более формально, учитывая три матрицы A, B и C, с записями из поля F, проблема проверки, имеет ли AB = C случайный O ( n 2 ) алгоритм...
Можно ли алгоритмически проверить, является ли вычисляемое число рациональным или целым? Другими словами, возможно ли для библиотеки, которая реализует вычислимые числа, предоставлять функции isIntegerили isRational? Я предполагаю, что это невозможно, и что это как-то связано с тем, что невозможно...
Предположим , что мы имеем полиномы степени не более 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 Поскольку...
Меня интересует явная булева функция со следующим свойством: если постоянна в некотором аффинном подпространстве , то размерность этого подпространства равна .е:0 , 1N→0 , 1е:0,1N→0,1f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}ееf о ( п )0 , 1N0,1N\\{0,1\\}^no ( n )о(N)o(n) Нетрудно показать, что...
Теория категорий и абстрактная алгебра имеют дело со способом, которым функции могут быть объединены с другими функциями. Теория сложности имеет дело с тем, насколько сложно вычислить функцию. Мне странно, что я не видел, чтобы кто-нибудь совмещал эти области изучения, поскольку они кажутся такими...
Каковы известные эффективные алгоритмы вычисления определителя целочисленной матрицы с коэффициентами в , кольца вычетов по модулю m . Число m может быть не простым, а составным (поэтому вычисления выполняются в кольце, а не в поле).ZмZм\mathbb{Z}_mммmммm Насколько я знаю (читайте ниже),...
2 вопроса для вычислительных геометров или алгебраистов: Я только начинаю погружаться в вычислительную геометрию, и мне это нравится =) Я пытаюсь прочитать знаменитую статью Гибаса и Столфи под названием «Примитивы для манипулирования общими подразделениями и вычисления диаграмм Вороного» с целью...
Читая статью об использовании алгебраических методов для обнаружения некоторых индуцированных подграфов, кажется, что реберный идеал является важным инструментом, соединяющим коммутативную алгебру и теорию графов. Поскольку я не знаком с вычислениями алгебраических объектов, есть ли хорошие ссылки...
В алгоритме Штрассена, чтобы вычислить произведение двух матриц и B , матрицы A и B делятся на блочные матрицы 2 × 2, и алгоритм продолжает рекурсивное вычисление 7- блочных матрично-матричных произведений, а не наивных 8- блочных матричных матриц. матричные произведения, т. е. если мы хотим C = A...
Для двух матриц A и B задача принятия решения о том, существует ли матрица перестановок P такая, что B = P - 1 A P , эквивалентна (граф изоморфизма). Но если мы расслабим P как просто обратимую матрицу, то в чем сложность? Существуют ли какие-либо другие ограничения на обратимую матрицу P , помимо...
Можете ли вы моделировать надежные трансляции в пи-исчислении? Если так: как? Если нет: есть ли подобные алгебры процессов, где вы можете? Что я пробовал: Если отправитель хочет послать сообщение у всего Р 1 до Р п , можно написать ! ( ¯ х года ) . S и x ( z ) . P 1 до x ( z ) . П н . Но как вы...
В 2012 году Липтон написал статью в блоге о новом алгоритме решения линейных систем над конечными полями Прасада Рагхавендры. Ссылка на проект документа Raghavendra по этой теме теперь мертв , и я не могу найти что - нибудь по этой теме на сайте Raghavendra в. Является ли результат правильным?...
Преобразование Уолша-Адамара (WHT) является обобщением преобразования Фурье и представляет собой ортогональное преобразование для вектора действительных или комплексных чисел размерности . Преобразование популярно в квантовых вычислениях, но недавно оно было изучено как своего рода предварительное...
Какова вычислительная сложность следующей задачи: с учетом двух комплексных матриц A и B проверить, есть ли матрица перестановок Р таким образом, что: В = Р Р Т .n × nN×Nn\times nAAAВВBппPB = PА ПT,Взнак равнопAпT,B = P A P^T. Если это помогает, можно предположить, что и B эрмитовы (или даже что A...
Рассмотрим следующую проблему: Входные данные : гиперплоскость ЧАС= { y ∈ RN:Tу = б }H={y∈Rn:aTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\} , задается вектором a ∈ ZNa∈Zn\mathbf{a} \in \mathbb{Z}^n и b ∈ Zb∈Zb \in \mathbb{Z} в стандартном двоичном представлении. Выход : x...
В разговорной речи определение показателя умножения матриц является наименьшим значением, для которого существует известный алгоритм умножения матриц . Это неприемлемо как формальное математическое определение, поэтому я предполагаю, что техническое определение является чем-то вроде инфимума по...
Учитывая матрицу m×nm×nm \times n (при условии, что m≥nm≥nm \ge n ), каков самый быстрый алгоритм для вычисления его ранга и базиса столбцов? Я знаю, что это может быть решено с помощью линейного пересечения матроидов, что подразумевает детерминистический алгоритм времени...
Вопрос. В своей работе « Улучшенное моделирование цепей стабилизатора» Ааронсон и Готтесман утверждают, что имитация схемы CNOT является ⊕L-полной (при сокращении пространства журнала). Ясно, что оно содержится в ⊕L ; как держится результат твердости? Эквивалентно: есть ли сокращение...
Я ищу информацию о вычислительной сложности матричного умножения прямоугольных матриц. Википедия утверждает, что сложность умножения на составляет (умножение в школьных учебниках).A∈Rm×nA∈Rm×nA \in \mathbb{R}^{m \times n}B∈Rn×pB∈Rn×pB \in \mathbb{R}^{n \times p}O(mnp)O(mnp)O(mnp) У меня есть...