Вопросы с тегом «algebraic-complexity»

38
Программа Малмули GCT

Иногда утверждают, что теория геометрической сложности Кетана Малмулей является единственной правдоподобной программой для решения открытых вопросов теории сложности, таких как вопрос P против NP. Было несколько положительных комментариев от известных теоретиков сложности о программе. По словам...

37
Имеет

Насколько я понимаю, программа теории геометрической сложности пытается разделить , доказав, что постоянство комплексной матрицы гораздо сложнее вычислить, чем определитель.VP≠VNPVP≠VNPVP \neq VNP Вопрос, который у меня возник после просмотра документов GCT: будет ли это сразу означать , или это...

36
Сложность тестирования значения по сравнению с вычислением функции

В общем, мы знаем, что сложность проверки того, принимает ли функция определенное значение на данном входе, проще, чем оценка функции на этом входе. Например: Оценка перманента неотрицательной целочисленной матрицы является # P-сложной, но при этом указывается, является ли такой перманент нулевым...

35
Умножение целых чисел, когда одно целое фиксировано

Пусть AAA будет фиксированным положительным целым числом размером nnn бит. Разрешается предварительно обрабатывать это целое число соответствующим образом. Учитывая другое положительное целое число BBB размером mmm битов, какова сложность умножения ABABAB ? Обратите внимание, что у нас уже есть...

23
Система доказательства суммы квадратов

Недавно я видел несколько статей об arxiv, которые ссылаются на систему доказательств под названием сумма квадратов. Может кто-нибудь объяснить, что такое доказательство суммы квадратов и почему такие доказательства важны / интересны? Как они связаны с другими алгебраическими системами...

18
Есть ли теория, которая сочетает в себе теорию категорий / абстрактную алгебру и вычислительную сложность?

Теория категорий и абстрактная алгебра имеют дело со способом, которым функции могут быть объединены с другими функциями. Теория сложности имеет дело с тем, насколько сложно вычислить функцию. Мне странно, что я не видел, чтобы кто-нибудь совмещал эти области изучения, поскольку они кажутся такими...

17
Формальное представление колец в вычислениях

Читая статью об использовании алгебраических методов для обнаружения некоторых индуцированных подграфов, кажется, что реберный идеал является важным инструментом, соединяющим коммутативную алгебру и теорию графов. Поскольку я не знаком с вычислениями алгебраических объектов, есть ли хорошие ссылки...

15
Известно ли, что существуют функции со следующим свойством прямой суммы?

Этот вопрос может быть задан либо в рамках сложности схем булевых схем, либо в рамках теории алгебраической сложности, либо, вероятно, во многих других ситуациях. Подсчитав аргументы, легко показать, что на N входах существуют булевы функции, для которых требуется экспоненциально много гейтов...

14
Гарантии твердости для AES

Многие криптосистемы с открытым ключом имеют доказуемую безопасность. Например, криптосистема Рабина доказуемо так же сложна, как и факторинг. Интересно, существует ли такая доказуемая безопасность для криптосистем с секретным ключом, таких как AES. Если нет, то каковы доказательства того, что...

14
Курс обучения алгебраической сложности

Я хочу узнать об алгебраических алгоритмах и их сложности. В частности, меня интересует PIT. Есть ли набор лекций, книг, статей и опросов для студентов, которые читали стандартный учебник по теории, такой как книга Сипсера или учебник по сложности Арора-Барака. Набор ссылок будет включать в себя...

14
VC размерность полиномов над тропическими полукольцами?

Как и в этом вопросе, я заинтересован в BPPBPP\mathbf{BPP} по сравнению с PP\mathbf{P} / polypoly\mathrm{poly} задачи для тропических (max,+)(max,+)(\max,+) и (min,+)(min,+)(\min,+) цепей. Этот вопрос сводится к показу верхних оценок размерности многочленов VC над тропическими полукольцами (см....

13
Емкость Уникально Решаемой Головоломки (USP)

В своей основополагающей работе Теоретико-групповые алгоритмы для умножения матриц Кон, Кляйнберг, Сегеди и Уманс вводят концепцию однозначно решаемой головоломки (определено ниже) и емкость USP. Они утверждают, что Копперсмит и Виноград, в своих собственных новаторских работах по умножению матриц...

13
Гауссово исключение с точки зрения группового действия

Гауссовское исключение делает определитель матрицы полиномиальным временем вычислимым. Снижение сложности в вычислении детерминанта, которое в противном случае является суммой экспоненциальных членов, обусловлено наличием альтернативных отрицательных признаков (отсутствие которых делает вычисление...

13
Наименьшая известная формула для определителя

Наименьшая известная формула для детерминанта имеет размер соответствии с фольклором (или Ран Разу в своей статье « Многолинейные формулы для перманента и детерминанта имеют суперполиномиальный размер» ).NO (журналн )NО(журнал⁡N)n^{\mathcal O(\log n)} У вас есть ссылки на это? В частности, что это...

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

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

12
Выражение определителя как постоянного

Одной из основных проблем в TCS является проблема выражения перманента в качестве детерминанта. Я читал статью Агравала « Детерминант против перманента», и в одном абзаце он утверждает, что обратная проблема проста. Легко видеть , что определитель матрицы может быть выражен как перманент...

12
автоморфизм в гаджетах Кая-Фюрера-Иммермана

В известном контрпримере для изоморфизма графа с помощью метода Вейсфейлера-Лемана (WL) в этой статье Кай, Фюрер и Иммерман построили следующий гаджет . Они строят граф определяемый какXk=(Vk,Ek)Xk=(Vk,Ek)X_k = (V_k, E_k) Vk=Ak∪Bk∪Mk where Ak={ai∣1≤i≤k},Bk={bi∣1≤i≤k}, and Mk={mS∣S⊆{1,2,…,k}, |S| is...

11
Детерминанты и умножение матриц. Сходство и различия в алгоритмической сложности и размере арифметической схемы

Я пытаюсь понять связь между алгоритмической сложностью и сложностью схемы детерминантов и умножения матриц. Известно, что определитель матрицы может быть вычислен за время ~ O ( M ( n ) ) , где M ( n ) - минимальное время, необходимое для умножения любых двух матриц n × n . Также известно, что...

11
Прямая сложность мономов

Пусть - некоторое поле. Как обычно, для f ∈ k [ x 1 , x 2 , … , x n ] мы определяем L ( f ) как прямолинейную сложность f над k . Пусть F - множество мономов f , а именно мономов, которые появляются в f с ненулевым коэффициентом.kkkf∈k[x1,x2,…,xn]f∈k[x1,x2,…,xn]f\in...

10
Определитель обобщенной матрицы Вандермонда

Матрица Мура похожа на матрицу Вандермонда, но имеет слегка измененное определение. http://en.wikipedia.org/wiki/Moore_matrix Какова сложность вычисления определителя заданной n × nn×nn \times n матрицы Мура полного ранга по модулю некоторого целого числа? Можно ли уменьшить определитель Мура с O (...