Я ищу реализацию алгоритма для вычисления ширины пути графа. Хорошо известно, что вычисление ширины пути эквивалентно вычислению числа поиска узла, числа разделения вершин или толщины интервала графа. Алгоритм не должен быть очень быстрым; Я хочу запустить его на графиках не более 20 вершин. Мне...
Я ищу ссылку (не доказательство того, что я могу сделать) на следующее расширение Черноффа. Пусть Икс1, . , , XNX1,..,XnX_1,..,X_n - булевы случайные величины, не обязательно независимые . Вместо этого гарантируется, что пг ( хя= 1 | С) < рPr(Xi=1|C)<pPr(X_i=1|C)(1+\lambda)np\right) Заранее...
В проблеме расширяемости нам дают часть решения, и мы хотим решить, можем ли мы расширить ее до полного решения. Некоторые проблемы расширяемости эффективно разрешимы, в то время как другие проблемы расширяемости превращают легкую проблему в сложную. Например, теорема Кенига-Холла утверждает, что...
Ветвление и ограничение - эффективная эвристика для задач поиска, и в Википедии перечислен ряд сложных проблем, где использовались ветвление и привязка. Тем не менее, мне не удалось найти ссылки, позволяющие предположить, что это больше, чем просто «один метод» решения этих проблем. Как ни странно,...
Есть ли проблемы, которые являются NP-полными при использовании евклидовой геометрии, но хорошо определены и разрешимы за полиномиальное время для некоторой неевклидовой...
Я ищу: Майкл О. Рабин, «Степень сложности вычисления функции и частичное упорядочение рекурсивных множеств», Еврейский университет, Иерусалим, 1960 Резюме: «Мы пытаемся измерить объем работы, свойственный задаче вычисления заданной вычислимой (рекурсивной) функции. Представлено и изучено понятие...
Какой самый быстрый известный детерминированный алгоритм может распознавать ориентированные графы с парой вершинных непересекающихся циклов? Я знаю, что графы с минимальной третьей степенью всегда имеют такую пару ( Thomassen'83 ), но даже в этом случае я не могу найти эффективный алгоритм в...
В определении (сильной) управляемости с фиксированными параметрами временная граница является выражением вида где входной экземпляр - ( x , k ) с параметром k , p - многочлен, а f - вычислимая функция.е( к ) . р ( | х | ) ,е(К),п(|Икс|),f(k).p(|x|),( х , к )(Икс,К)(x,k)ККkппpееf Можно заменить...
У меня есть вопрос, касающийся СЕРФ-сводимости Impagliazzo, Paturi и Zane и субэкспоненциальных алгоритмов. Определение SERF-сводимости дает следующее: Если P1P1P_1 является SERF-сводимым к P2P2P_2 и существует алгоритм O(2εn)O(2εn)O(2^{\varepsilon n}) для P2P2P_2 для каждого...
Я заинтересован в моделировании объектов, от объектно-ориентированного программирования, в теории зависимых типов. В качестве возможного приложения я хотел бы иметь модель, в которой я могу описать различные функции императивных языков программирования. Я мог найти только одну статью о...
Определение чисел Рамси следующее: Пусть положительное число такого , что каждый граф порядка по крайней мере содержит либо клику на вершину или множество стабильного на вершинах.R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)R(a,b)aaabbb Я работаю над некоторым расширением номеров Рамси. Хотя исследование...
Меня интересует сложность задачи о доминирующем множестве (DSP) в некоторых конкретных классах графов, которые являются подклассами хордовых графов . Граф является неориентированным графом путей, если он является графом пересечения вершин семейства путей в некотором неориентированном дереве. Пусть...
Для данного плоского графа его можно вложить в линейное время, свободно переходя в сетку . Меня интересует, известны ли какие-либо эффективные алгоритмы, позволяющие прямой линии встраивать планарный граф, свободно пересекающийся в сетку n c × n c , для некоторого малого c , такого, чтобы...
Легко видеть, что если то есть общие проблемы поиска N P, которые не могут быть решены за полиномиальное время (создайте проблему общего поиска, имея как свидетелей для членства, так и свидетелей для не состоятельности).Н П∩coNP≠PNP∩coNP≠P\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}NPNп\mathsf{NP}...
Известно ли, что задача множества вершин обратной связи на неориентированных плоских графах ограниченной степени является трудной?Н
Для булевой функции влияние й переменной определяется как где строка, полученная путем переключения го бита . Тогда минимальное влияние - этоf:{−1,1}n→{−1,1}f:{−1,1}n→{−1,1}f\colon\{-1,1\}^n \to \{-1,1\}iiiInfi[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)]Infi[f]=defPrx∼{−1,1}n[f(x)≠f(x⊕i)]...
Чтобы отпраздновать 100-летие Алана Тьюринга, я хочу посмотреть документальный фильм о его жизни. Однако есть несколько документальных фильмов на выбор. Какой документальный фильм об Алане Тьюринге ваш любимый? Пожалуйста, включите только один документальный фильм за...
Мотивация: соавтор редактирует рукопись, и я хотел бы увидеть четкое резюме изменений. Все инструменты, подобные "diff", как правило, бесполезны, если вы одновременно перемещаете текст (например, реорганизуете структуру) и делаете локальные правки. Неужели так сложно понять это правильно?...
Наименьшая известная формула для детерминанта имеет размер соответствии с фольклором (или Ран Разу в своей статье « Многолинейные формулы для перманента и детерминанта имеют суперполиномиальный размер» ).NO (журналн )NО(журналN)n^{\mathcal O(\log n)} У вас есть ссылки на это? В частности, что это...
Мне кажется, что специалисты по машинному обучению / интеллектуальному анализу данных знакомы с P и NP, но редко говорят о некоторых более тонких классах сложности (например, NC, BPP или IP) и их последствиях для эффективного анализа данных. Есть ли какой-нибудь обзор работы, выполняющей...