Пусть - некоторый язык, тогда мы определим синтаксическую конгруэнцию как u ∼ v : ⇔ ∀ x , y ∈ X ∗ : x u y ∈ L ↔ x v y ∈ L и фактор-моноид X ∗ / ∼ L равен называется синтаксическим моноид из L .L⊆X∗L⊆X∗L \subseteq X^{\ast}u∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈Lu∼v:⇔∀x,y∈X∗:xuy∈L↔xvy∈L u \sim v :\Leftrightarrow...
Вопрос. В своей работе « Улучшенное моделирование цепей стабилизатора» Ааронсон и Готтесман утверждают, что имитация схемы CNOT является ⊕L-полной (при сокращении пространства журнала). Ясно, что оно содержится в ⊕L ; как держится результат твердости? Эквивалентно: есть ли сокращение...
Рассмотрим вектор переменных и набор линейных ограничений, заданных как .x⃗ x→\vec{x}Ax⃗ ≤bAx→≤bA\vec{x}\leq b Кроме того, рассмотрим два многогранника P1P2={(f1(x⃗ ),⋯,fm(x⃗ ))∣Ax⃗ ≤b}={(g1(x⃗ ),⋯,gm(x⃗ ))∣Ax⃗ ≤b}P1={(f1(x→),⋯,fm(x→))∣Ax→≤b}P2={(g1(x→),⋯,gm(x→))∣Ax→≤b}\begin{align*}...
Существует ли , NP- или P-полный язык, имеющий некоторое семейство групп симметрии (или группоид , но тогда алгоритмические вопросы становятся более открытыми), действующий (за полиномиальное время) на множествах такой, что орбит мало, т. е. такой, что для достаточно больших и некоторого c , и...
Робин Милнер определил биграфы как тип графической структуры с графоподобной структурой, где узлы могут быть вложенными. Они обобщают исчисления процессов, такие как CCS и калькуляция, но Мильнер, похоже, намеревался использовать их гораздо более широко: в записках семинара незадолго до его смерти...
Многие криптосистемы с открытым ключом имеют доказуемую безопасность. Например, криптосистема Рабина доказуемо так же сложна, как и факторинг. Интересно, существует ли такая доказуемая безопасность для криптосистем с секретным ключом, таких как AES. Если нет, то каковы доказательства того, что...
Что известно о классе языков, распознаваемых конечными автоматами, имеющими одинаковое начальное и принимающее состояние? Это правильное подмножество обычных языков (поскольку каждый такой язык содержит пустую строку), но насколько он слаб? Есть ли простая алгебраическая характеристика? То же самое...
Дана матрица A с рациональными элементами. В чем сложность проверки А диагонализируемой?n × nN×Nn\times nAAAAAA Я подозреваю, что это может быть сделано в P, но я не знаю никаких ссылок. Однако, более интересный вопрос, есть ли лучший класс сложности для решения этой проблемы? Любое руководство /...
У меня есть вопрос, касающийся полиномов и вероятностей низкой степени: какова (асиптотическое поведение) вероятность того, что случайный * полином ppp по GF (2) со степенью и n переменных имеет .≤d≤d\le...
У меня есть алгебраическая задача, связанная с векторами в поле GF (2). Пусть v1,v2,…,vmv1,v2,…,vmv_1, v_2, \ldots, v_m - (0,1) -векторы размерности nnn и m=nO(1)m=nO(1)m=n^{O(1)} . Найти алгоритм полиномиального времени, который находит (0,1) -вектор uuu такой же размерности, чтобы uuu не было...
Пусть квадрат n × nN×Nn\times n вещественной матрицы AA{\bf A} и два вектора ИксИкс{\bf x} и бб{\bf b} длины NNn такие, что A x = b .AИксзнак равноб,{\bf A}{\bf x}={\bf b}. Решение для ИксИкс{\bf x} помощью стандартного исключения Гаусса дает совокупную сложность почти O ( n3)О(N3)O(n^3) . Однако...
Насколько сложно найти самое редкое решение системы линейных уравнений? Более формально рассмотрим следующую проблему решения: Экземпляр: система линейных уравнений с целыми коэффициентами и числом ccc . Вопрос: существует ли решение для системы с хотя бы ccc переменными, присвоенными нулю? Я также...
Я искал о матричном умножении, поэтому я впервые посещал вики- алгоритмы умножения матриц, в ссылках я нашел статью, в которой утверждается, что используется алгоритм O ( n2л о г( н ) )О(N2Lограмм(N))O(n^2 log(n)) , я собираюсь прочитать статью, но она сложная и Уилл читает слишком много времени,...
Я имею опыт работы в теории / логике сложности (где большую часть времени занимает только один процесс) и в распределенных вычислениях (где есть процессов, и один или несколько могут со временем выйти из строя). Однако теперь я хочу сказать что-то о процессе, порождающем / создающем / порождающем...
Мы знаем, например, из Koutis-Miller-Peng (на основе работы Spielman & Teng), что мы можем очень быстро решить линейные системы Ax=bAx=bA x = b для матриц AAA которые представляют собой матрицу Лапласа графа для некоторого разреженного графа с неотрицательными весами ребер , Теперь (первый...
Я ищу список об известной или неизвестной сложности различных теоретико-алгебраических задач. Например, GCD в открыт,NC1NC1NC^1 факторинг в открыт,PPP вычисление когомологий пучка -hard#P#P\#P , Арора и Барак утверждают, что вариант факторинга является -полным (хотя это не ясно из обсуждения в...
Предположим, мы хотим умножить матриц. Алгоритм медленного умножения матриц выполняется за время O ( n 3 ) и использует O ( n 2 ) памяти. Самое быстрое умножение матриц выполняется за время n ω + o ( 1 ) , где ω - постоянная линейной алгебры, но что известно о ее сложности памяти?n×nn×nn \times...
На cs.stackexchange я спросил о scala-библиотеке algebird на github, размышляя о том, почему им может понадобиться пакет абстрактной алгебры. Страница GitHub имеет несколько подсказок: Реализации Monoids для интересных алгоритмов аппроксимации, таких как фильтр Блума, HyperLogLog и CountMinSketch....
Пусть вещественная матрица ( ) обладает тем свойством, что любой набор из столбцов имеет полный ранг.k × nК×Nk\times nk ≤ nК≤Nk\le nAA{\bf A}ККk В: Существует ли эффективный способ детерминированного поиска вектора такой, что расширенная матрица сохраняет то же свойство, что и : любые столбцов...
РЕДАКТИРОВАТЬ (Тара B): Я все еще был бы заинтересован в ссылке на доказательство этого, так как я должен был доказать это сам для моей собственной статьи. Я ищу доказательство теоремы 4, которое появляется в этой статье: Бесконечная иерархия пересечений контекстно-свободных языков Лю и Вейнера....