Слово www называется примитивным , если нет слов и так что . Множество всех примитивных слов над алфавитом является хорошо известным языком. WLOG мы можем выбрать . vvvk>1k>1k > 1w=vkw=vkw = v^kQQQΣΣ\SigmaΣ={a,b}Σ={a,b}\Sigma = \{ a,b \} Язык является простой , если для каждого языка и с мы...
Часто говорят, что при использовании алгоритма MD5 для подписания некоторой произвольной информации общий секрет должен быть в конце.
Двадцать лет назад я создал пакет регулярных выражений, который включал преобразования из регулярных выражений в конечный автомат (DFA) и поддерживал множество закрытых операций с регулярными выражениями (звезда Клина, конкатенация, обратное, операции над множествами и т. Д.). Я не был уверен в...
Для языка L ⊆ Σ ^ * определите синтаксическую конгруэнцию ≡ в L как наименьшую конгруэнцию на Σ ^ *, которая насыщает L , т.е. u ≡ v ⇔ (∀ x, y) [xuy ∈ L ↔ xvy ∈ L]. Теперь определим эквивалентность Nerode как следующее правильное сравнение: u ∼ v ⇔ (∀ x) [ux ∈ L ↔ vx ∈ L]. Пусть [u] - класс...
Бета-эта-теория лямбда-исчисления является пост-полной. Можно ли добавить дополнительные правила, чтобы расширить бета-теорию лямбда-исчисления, чтобы получить противоречивые теории, помимо теории бета-эта? постскриптум Этот вопрос противоречил моему собственному правилу, согласно которому вопросы...
Это продолжение этого вопроса на math.stackexchange. Допустим, что непустое множество S ⊆ ℤ является самонесущим, если для каждого a ∈ S существуют различные элементы b, c ∈ S, такие что a = b + c. Для натуральных чисел n простые примеры включают идеал S = n ℤ или (для n > 3) целочисленный...
Adleman, FOCS'78 показал, что любая рандомизированная схема для входов длины может быть неравномерно дерандомизирована. Однако конструкция эффективно дублирует исходную схему O ( п ) раз, так что derandomized цепи больше , чем оригинал с коэффициентом O ( п ) . Есть ли более эффективная...
В [1] Turan показывает, что чувствительность (называемая в статье «критической сложностью») свойства графа строго больше, чем гдеm- количество вершин в графе. Он продолжает предполагать, что любое нетривиальное свойство графа имеет чувствительность≥m-1. Он упоминает, что это было проверено дляm≤5....
Как и в области статей в журнале ACM по экспериментальной алгоритмической JEA . Какие были основополагающие работы? Каковы основные результаты? Как они характеризуются? Какие-нибудь интересные связи с другими областями...
Знаменитая картина мира Нила Иммермана выглядит следующим образом (нажмите, чтобы увеличить): Его «действительно выполнимый» класс не включает другого класса; мой вопрос тогда: Что такое проблема AC 0, которая считается непрактичной и почему?...
-fixed точки без проблем автоморфизма запрашивает автоморфизм графа , который перемещается по крайней мере , к ( п ) узлы. Проблема в том, что N P- полна, если k ( n ) = n c для любого c > 0.kkkk(n)k(n)k(n)NPNPNPk(n)=nck(n)=nck(n)=n^cccc Однако, если то задача полиномиального времени Тьюринга...
LogCFL - это набор всех языков, пространство логирования которых сводится к языку без контекста. Аналогично, LogDCFL - это набор всех языков, пространство логирования которых сводится к детерминированному контекстно-свободному языку. Смотрите эту статью в Википедии, чтобы узнать о некоторых...
Единственный пробел, который я всегда осознавал, что я на самом деле не понимаю, - это неравномерная и равномерная вычислительная сложность, где сложность схемы представляет собой неоднородную версию, а машины Тьюринга - это вещи, которые являются однородными. Я предполагаю, что «равномерный» - это...
Меня интересуют два вопроса относительно контекстно-зависимых языков (CSL) и полноты: Существует ли понятие полноты для CSL и какие языки являются законченными? Существуют ли естественные CSL, которые являются NP-полными? Для 2. я, конечно, могу думать о естественных NP-полных языках, которые...
Предположим, нам дана матрица n по n, M, с целочисленными элементами. Можем ли мы решить в P, существует ли перестановка такая, что для всех перестановок мы имеем ?σσ\sigmaπ≠ σπ≠σ\pi\ne\sigmaΠ Мя σ( я )≠ П Мя π( я )ΠMяσ(я)≠ΠMяπ(я)\Pi M_{i\sigma(i)}\ne \Pi M_{i\pi(i)} Замечания. Конечно, можно...
Блум, Микали и Фельдман (BFM) выдвинули новую (криптографическую) модель, в которой все стороны (честные или состязательные) имеют доступ к некоторой строке. Предполагается, что строка выбирается в соответствии с некоторым распределением (обычно равномерным) доверенной стороной. Это называется...
Фон : В оригинальной статье UGC Субхаша Хота ( PDF ) он доказывает, что UG-сложность определения того, допускает ли заданный экземпляр CSP ограничения всех форм Не-все-равные (a, b, c) по троичному алфавиту 1 - ограничений или не существует никаких заданий, удовлетворяющих 8ϵϵ\epsilonиз...
Нисан доказал в «Псевдослучайных генераторах для пространственно-ограниченных вычислений», что существует псевдослучайный генератор, который «обманывает» ограниченные в пространстве вычисления. Эта конструкция справедлива для каждого оракула (по крайней мере, для неадаптивных...
Я ищу примеры методов доказательства цены границ анархии, которые способны отделить цену анархии от грубого коррелированного равновесия (ограничивающий набор динамики без внешнего сожаления) от цены анархии над коррелированным равновесием (ограничивающий комплектация без своп-сожалений). Известны...
Я думал о варианте гексагона , где вместо двух игроков поочередно делают ходы, каждый ход, выбранный случайным образом, делает ход. Насколько сложно определить шансы каждого игрока на победу? Эта проблема, очевидно, есть в PSPACE, но не может ли она быть NP-сложной, а тем более PSPACE-полной....