Если мы можем доказать, что , означает ли это, что ?L=PL=P\mathsf{L}=\mathsf{P}NL=NPNL=NP\mathsf{NL}=\mathsf{NP} Я думал, что это так, но я не могу доказать это (также для
Учитывая направленный граф, мы хотим решить, содержит ли он направленный цикл четной длины. В этой статье 1997 года, написанной YUSTER и ZWICK, утверждается, что проблема не в том, что она находится в а также в том, что она не является N P -полной.ппPNпNпNP Есть ли какой-либо недавний результат,...
Мы можем сделать свертку в для полиномов плюс / умножение с FFT. Тем не менее, подход не кажется очень обобщенным для колец в целом. Был ли какой-нибудь прогресс по наивной свертке для кольца max / plus?O ( n logн )О(NжурналN)O(n\log n)O ( n2)О(N2)O(n^2) Я должен отметить, что можно преобразовать...
Сложна ли задача NPF SAT NP, когда общее число (но не ширина) предложений из 3 или более членов ограничено сверху константой? А что конкретно, когда есть только один такой...
Детерминированный автомат называется k- локальным при k > 0, если для каждого w ∈ X k множество { δ ( q , w ) : q ∈ Q } содержит не более один элемент. Интуитивно это означает, что если слово w длины k приводит к состоянию, то это состояние уникально или сказано иначе, чем произвольное слово...
Известно, что для ошибки определение рандомизированной сложности связи в худшем случае и определение среднего случая эквивалентны. Но когда ошибка равна , сложность рандомизированной связи в худшем случае такая же, как сложность детерминированной связи.Θ(1)Θ(1)\Theta(1)000 Известно ли, что любая...
Распределенные алгоритмы, которые устойчивы к сбоям, могут быть либо детерминированными, либо вероятностными. Возьмите для примера проблему консенсуса. Paxos является детерминированным в том смысле, что, учитывая допущение, оно всегда работает. В противоположность этому рандомизированный консенсус...
В главе 13 «Атомные объекты» книги «Распределенные алгоритмы» Нэнси Линч доказано, что линеаризуемость (также известная как атомарность) является свойством безопасности. То есть его соответствующее свойство trace непусто, закрыто по префиксу и закрыто по пределу , как определено в разделе 8.5.3....
Известны алгоритмы полиномиального времени для нахождения порождающих множеств групп перестановок, что интересно, поскольку мы можем затем представить эти группы кратко, не отказываясь от алгоритмов полиномиального времени для ответа на многие интересные вопросы, связанные с этими группами. Однако...
Минимизация схемы - это проблема минимизации размера данной схемы. Есть ли что-нибудь подобное для общих программ? В частности, мой вопрос - Существуют ли алгоритмы, чтобы минимизировать количество инструкций для данной программы. Я знаю, что это неразрешимая проблема, но я не ищу решение, которое...
Мы знаем, что бета-равенство просто типизированных лямбда-терминов разрешимо. Учитывая M, N: σ → τ, разрешимо ли для всех X: σ, MX
Этот вопрос касается того, существуют ли какие-либо известные обратимые тарпиты Тьюринга, где «обратимый» означает в смысле Аксельсена и Глюка , а «тарпит» является гораздо более неформальным понятием (и, возможно, не очень удачным выбором слова), но я сделаю все возможное, чтобы объяснить, что я...
Существуют ли классы графов, для которых ширина дерева ограничена сверху функцией числа клика , т.е. ?tw(G)tw(G)tw(G)ω(G)ω(G)\omega(G)tw(G)≤f(ω(G))tw(G)≤f(ω(G))tw(G)\leq f(\omega(G)) Например, это классический факт, что для любого хордального графа мы имеем . Таким образом, классы, связанные с...
Меня интересуют алгоритмы для конечных групп, реализованные в пакете GAP. Кажется, что все известные алгоритмы в этой области имеют дело с группами перестановок / матричными группами; Двумя фундаментальными являются Schreier-Sims [1970] и Butler [1979], см., например, «Алгоритмы для групп...
Неравенство Фано может быть изложено во многих формах, и одна особенно полезная из-за (с незначительной модификацией) Одеда Регева : Пусть XXX - случайная величина, и пусть Y= г( Х)Y=g(X)Y = g(X) где г( ⋅ )g(⋅)g(\cdot) - случайный процесс. Предположим, что существует процедура еff которой Y= г( х...
Дополнительную расслабленность (CS) обычно учат, когда говорят о двойственности. Он устанавливает хорошее соотношение между основным и двойственным ограничением / переменными с математической точки зрения. Две основные причины применения CS (как преподается в аспирантуре и учебниках): Для проверки...
Некоторое время я очень интересовался теорией языка программирования и процессными исчислениями и начал их изучать. Честно говоря, это то, что я не прочь заняться карьерой. Я считаю, что теория невероятно увлекательна. Один постоянный вопрос, с которым я постоянно сталкиваюсь, заключается в том,...
Я наткнулся на открытую проблему, поставленную Дэвидом Эппштейном, и меня интересует ее сложность. Он предположил, что он NP-завершен. Ввод: по n матриц 0 и 1, последовательность n 2 0 и 1nnnnnnn2n2n^2 Вопрос: существует ли путь через соседние элементы матрицы, охватывающий каждую запись матрицы...
Учитывая два многогранник и Q , P и Q является равносоставлены , если существует конечные множества многогранников P 1 , ... , P п и Q 1 , ... , Q п таких , что P я и Q я конгруэнтен для всех I , P = ∪ п я = 1 Р я и Q = ∪ п я = 1 QпPPQQQпPPQQQP1,…,PnP1,…,PnP_1, \ldots, P_nQ1,…,QnQ1,…,QnQ_1, \ldots,...
Давайте назовем язык NP редко сертифицированным тогда и только тогда, когда:L ∈L∈L \in Существует такой многочлен , что для каждого входа x ∈ Σ ∗ размера n , если x ∈ L, то множество U x сертификатов u, которые проверяют, что x ∈ L имеет полиномиальный размер, т. Е. | U x | ≤ p ( n ) .p : N →...