В курсах автоматов стандартным доказательством является то, что для L=Σ⋆L=Σ⋆L = \Sigma^\star и |Σ|≥2|Σ|≥2|\Sigma| \ge 2 что не является контекстно-свободным языком.S(L)={ww:w∈L}S(L)={ww:w∈L}S(L) = \{ww : w \in L\} Это также верно , что для любого конечного , S ( L ) конечна (и , следовательно,...
Отказ от ответственности: я очень мало знаю о теории сложности. Извините, но на самом деле нет способа задать этот вопрос, не будучи (ужасно) лаконичным: Какими должны быть морфизмы в «категории» машин Тьюринга? Это, очевидно, субъективно и зависит от толкования теории, поэтому в идеале ответ на...
Мой студент недавно задал следующий вопрос: D T I M E ( f ( n ) ) ⊊ D T I M E ( g ( n ) ) . DTIME(f(n))⊊DTIME(g(n)).DTIME(f(n)) \subsetneq DTIME(g(n)).h ( n ) h(n)h(n)D T I M E ( f ( n ) ) ⊊ D T I M E ( h ( n ) ) ⊊ D T I M E ( g ( n)) ) ?DTIME(f(n))⊊DTIME(h(n))⊊DTIME(g(n))?DTIME(f(n)) \subsetneq...
Недавно Бабай опубликовал статью о STOC 2016, в которой утверждается, что изоморфизм графов можно решить за квазиполиномиальное время. В начале 2017 года Бабай отозвал квазиполиномиальное требование из-за некоторых серьезных ошибок, обнаруженных Харальдом Хельфготтом. Как объяснил сам Бабай, этот...
Теорема Савича показывает, что для всех достаточно больших функций , и доказательство того, что это тесно, является открытой проблемой на протяжении десятилетий ,NSPACE(f(n))⊆DSPACE(f(n)2)NSPACE(f(n))⊆DSPACE(f(n)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)fff Предположим, мы подходим к...
Меня интересует сортировка массива положительных целочисленных значений за линейное время (в модели оперативной памяти с одинаковой мерой стоимости, т. Е. Целые числа могут иметь размер до логарифмического, но предполагается, что арифметические операции над ними будут выполняться единица времени)....
Известно, что пересечение трех общих матроидов является NP-трудным ( источником ), что осуществляется посредством сокращения из гамильтонова цикла. Сокращение использует один графический матроид и два матроида связи. Частный случай проблемы, над которой я работаю, может быть решен путем пересечения...
В «Квантовых вычислениях и квантовой информации» Майка и Айка алгоритм Гровера объясняется очень подробно. Тем не менее, в книге и во всех объяснениях, которые я нашел в Интернете для алгоритма Гровера, кажется, нет упоминания о том, как устроен Оракул Гровера, если только мы уже не знаем, какое...
Мы знаем (на данный момент около 40 лет, спасибо Адлеману, Беннету и Джиллу), что включение BPP P / poly и еще более сильное BPP / poly P / poly имеют место. «/ Poly» означает, что мы работаем неравномерно (отдельная схема для каждой входной длины ), в то время как P без этой «/ poly» означает, что...
Для простого неориентированного графа GGG найдите подмножество A≠∅A≠∅A\neq \emptyset вершин, такое что для любой вершины хотя бы половина соседей также находится в , иx∈Ax∈Ax\in AxxxAAA размер AAA минимален. То есть мы ищем кластер, в котором по крайней мере половина окрестности каждой внутренней...
Обычно используемые алгоритмы хэширования паролей работают сегодня так: солить пароль и подавать его в KDF. Например, используя PBKDF2-HMAC-SHA1, процесс хеширования пароля DK = PBKDF2(HMAC, Password, Salt, ...). Поскольку HMAC представляет собой двухэтапное хеширование с дополненными клавишами, а...
Существуют ли интересные примеры алгоритмов, которые были опубликованы с проверенными границами, и где позже были опубликованы строго лучшие оценки? Не лучшие алгоритмы с лучшими оценками - очевидно, что это случилось! Но лучший анализ ведет к лучшей оценке существующего алгоритма Я думал, что...
Как называется следующий вариант обложки набора? Для заданного набора S, набора C подмножеств S и целого положительного числа K существуют ли K наборов в C, так что каждая пара элементов S лежит в одном из выбранных подмножеств. Примечание. Нетрудно понять, что эта проблема является NP-полной:...
Этот вопрос относится к алгоритму Фишера-Йейтса для возврата случайного перемешивания данного массива. На странице Википедии написано, что ее сложность составляет O (n), но я думаю, что это O (n log n). На каждой итерации i случайное целое число выбирается между 1 и i. Простое запись целого числа в...
Я ищу онлайновый алгоритм для поддержания транзитивного замыкания ориентированного ациклического графа с временной сложностью меньше, чем O (N ^ 2) на каждое добавление ребра. Мой текущий алгоритм выглядит так: For every new edge u->v connect all nodes in Pred(u) \cup { u } with all nodes in...
Учитывая язык L, определенный машиной Тьюринга, который его решает, возможно ли алгоритмически определить, лежит ли L в
Задача P называется в APX, если существует некоторая постоянная c> 0 такая, что для P существует алгоритм аппроксимации за полиномиальное время с коэффициентом аппроксимации 1 + c. APX содержит PTAS (это можно увидеть, просто выбрав любую константу c> 0) и P. APX в NP? В частности, означает...
Существуют ли сейчас более простые алгоритмы / доказательства триангуляции плоского многоугольника за линейное время? Что является хорошим ресурсом о состоянии этой знаменитой...
В этой статье Эрика Д. Деймэна, Сандора П. Фекете, Роберта Дж. Ланга «Упаковка кругов для дизайна оригами сложно» на странице 15, рис. 13, они утверждают, что длина стороны наименьшего квадрата, заключающего два круга области 1/2 каждый составляет 1,471299. По моим расчетам я получаю длину стороны...
Пытаясь доказать некоторые базовые свойства с помощью коиндуктивных типов в Coq, я продолжаю сталкиваться со следующей проблемой и не могу ее обойти. Я перевел проблему в простой сценарий Coq следующим образом. Типа дерево определяет , возможно , бесконечные дерева с ветвями , меченных с элементами...