Есть ли известный результат по классу сложности 1-в-3-SAT с ограниченным числом вхождений переменных? Я придумал следующее экономное сокращение с Питером Найтингейлом, но я хочу процитировать кое-что, если это известно. Вот трюк, который мы придумали. Это показывает, что 1-в-3-SAT, ограниченный...
Антицепь в DAG представляет собой подмножество ⊆ V вершин, попарно недостижим, а именно, нет v ≠ v ' ∈ таким образом, что v достижима из V ' в Е . Из теоремы Дилворта в теории частичного порядка известно, что если DAG не имеет антицепи размера k ∈ N , то она может быть разложена в объединение не...
Пусть язык и f : Σ ⋆ × Σ ⋆ → Σ ⋆ функция по двум параметрам со свойством, которое для всех x и y , f возвращает элемент из L тогда и только тогда, когда x и y являются элементами из L :LLLе: Σ⋆× Σ⋆→ Σ⋆f:Σ⋆×Σ⋆→Σ⋆f\colon {\Sigma^\star}\times\Sigma^\star\to\Sigma^\starxxxyyyfffLLLxxxyyyLLL...
В монадической логике первого порядка, также известной как монадический класс задачи решения, все предикаты принимают один аргумент. Аккерманн показал, что он может быть разрешен и НЕОБХОДИМО завершен . Однако такие проблемы, как SAT и SMT, имеют быстрые алгоритмы их решения, несмотря на...
У меня есть набор из nnn двоичных векторов S={s1,…,sn}⊆{0,1}k∖{1k}S={s1,…,sn}⊆{0,1}k∖{1k}S = \{s_1, \ldots, s_n \} \subseteq \{0,1\}^k \setminus \{1^k\} и целевой вектор t=1kt=1kt = 1^k который является вектором «все единицы». Гипотеза: если ttt можно записать как линейную комбинацию элементов SSS...
Меня интересует классическая проблема РЕГУЛЯРНОГО ВКЛЮЧЕНИЯ ЯЗЫКА. Для регулярного выражения обозначим через L ( E ) связанный с ним регулярный язык. (Регулярные выражения на фиксированном алфавите Σ с объединением операций, звездой Клини и конкатенацией.)ЕЕEL ( E)L(Е)L(E)ΣΣ\Sigma Входные данные:...
Я читал о наследственной замене Простого лямбда-исчисления и Логической структуры с различными терминами и типами. Мне интересно, есть ли примеры наследственного замещения в зависимо типизированной системе с иерархией юниверсов? то есть где и т. д.True:Set0:Set1:Set2True:Set0:Set1:Set2 True : Set_0...
В частности, я прошу ресурсы, чтобы узнать о системах машинного обучения, которые могут обновлять свои соответствующие сети убеждений (или эквивалент) во время работы. Я даже сталкивался с несколькими, хотя не смог их добавить в закладки. Как вы можете себе представить, это довольно сложная тема...
Какие документы по обработке ошибок в распределенных системах вы
Во-первых, я до сих пор не уверен, хорошо ли подходит этот вопрос для этого вопроса, поэтому я не буду обижаться, если толпа думает, что это не так ... В поисковом маркетинге несколько проблем интересны. Разработка справедливых (и прибыльных) аукционных механизмов и расчет оптимальных стратегий...
Этот вопрос в том же духе, что и вдохновляющие разговоры для учеников старших классов . Мой доктор философии консультант попросил меня дать вдохновляющую лекцию для нового M.Sc. студенты. Предмет - основы криптографии , которая лучше всего иллюстрируется книгой Гольдрайха . Беседа займет около...
Меня интересуют примеры конструкций в теории сложности, которые лучше случайных. Я знаю только один пример такой конструкции в области кодов, исправляющих ошибки. Коды алгебраической геометрии лучше в некотором диапазоне параметров, чем случайные коды. Можно легко построить такие искусственные...
Span-программа - это линейно-алгебраический способ задания булевой функции, представленный здесь . Недавно эта модель использовалась, чтобы показать, что метод отрицательного противника обеспечивает точную характеристику (по крайней мере, до ) сложности квантовых...
Хотя экспоненциальное разделение между сложностью квантового запроса с ограниченной ошибкой ( Q ( f)Q(f)Q(f) ) и сложностью детерминированного запроса ( Д ( ф)D(f)D(f) ) или сложностью рандомизированного запроса с ограниченной ошибкой ( R ( f)R(f)R(f) ) известно, они применяются только к...
Была проделана большая работа по вычислительным задачам для частичных порядков (например, распознавание, число переходов, распознавание графа сравнимости и т. Д.). Мне любопытно, какая работа, связанная с решетками, была проделана. Я искал вокруг и не нашел много похожих работ для решеток. В...
Мне любопытно, если бы кто-то мог порекомендовать какой-нибудь дополнительный материал для более глубокого понимания статьи: « Некоторые результаты и проблемы о квантовых неравенствах типа Белла - Цирельсон ». В частности, кое-что, что может более подробно рассказать о геометрической интерпретации...
Вот вопрос «следа B», если таковой был. Резюме: первое, о чем я думаю, когда пытаюсь дать семантику недетерминированным программам, приводит к семантике, где я не могу доказать вещи о циклах, которые заканчивают только недетерминированно. Конечно, кто-то определил, что делать в этой ситуации, или,...
Мой вопрос касается эквивалентности безопасности различных односторонних функций-кандидатов, которые могут быть построены на основе сложности факторинга. Предполагая проблему ФАКТОРИНГ: [Дано для случайных простых чисел , найти , ]P , Q < 2 n P QN=PQN=PQN = PQP,Q<2nP,Q<2nP, Q < 2^nPPPQQQ...
Для смешанного графа с ребрами E и дугами A найдите совпадение в E, которое минимизирует количество дуг в G / M , где G / M получается из G путем сжатия совпадающих вершин и удаления параллельные дуги.G=(V,E,A)G=(V,E,A)G=(V,E,A)EEEAAAEEEG/MG/MG/MG/MG/MG/MGGG Является ли (вариант решения) этой...
Предположим, что - булев язык из конечных строк над . Пусть будет количеством строк в с длиной . Для функции от натуральных чисел до натуральных чисел имеет верхнюю плотность если для всех достаточно больших .{ 0 , 1 } L n L n d ( n ) L d ( n ) L n ≤ 2 n d ( n ) nLLL{ 0 , 1...