Существует два основных типа сбоев процессора в моделях распределенных вычислений: (1) Сбои: процессор останавливается и больше не запускается. (2) Византийские сбои: процессоры ведут себя соперничающе, злонамеренно. Мой вопрос: Каковы некоторые другие типы отказов процессора, которые были изучены,...
Легко видеть, что если то есть общие проблемы поиска N P, которые не могут быть решены за полиномиальное время (создайте проблему общего поиска, имея как свидетелей для членства, так и свидетелей для не состоятельности).Н П∩coNP≠PNP∩coNP≠P\mathsf{NP}\cap\mathsf{coNP} \neq \mathsf{P}NPNп\mathsf{NP}...
Недавно я изучал введение в голографические алгоритмы. Я столкнулся с некоторыми комбинаторными объектами, которые называются пфаффианцами. Я не очень много знаю о них на данный момент и натолкнулся на некоторые неожиданные способы их использования. Например, я узнал, что их можно использовать для...
Пока пишу небольшой пост о сложности видеоигр Nibbler и Snake ; Я обнаружил, что они оба могут быть смоделированы как задачи реконфигурации на плоских графах; и кажется маловероятным, что такие проблемы не были хорошо изучены в области планирования движения (представьте, например, цепочку связанных...
Пытаясь решить проблему, я выразил ее часть в виде следующей целочисленной линейной программы. Здесь - все натуральные числа, заданные как часть входных данных. Указанное подмножество переменных x i j устанавливается в ноль, а остальные могут принимать положительные целые...
Treewidth и pathwidth являются популярными параметрами, измеряющими близость графа к дереву или пути, соответственно. В самом деле, кажется, что древовидная ширина настолько популярна, что во многих статьях, книгах и конспектах лекций, которые (даже очень осторожно) знакомят с алгоритмическими...
Фиксированный параметр и аппроксимация - это совершенно разные подходы для решения сложных задач. У них разная мотивация. Приближение ищет более быстрый результат с приближенным решением. Фиксированный параметр ищет точное решение с временной сложностью в терминах экспоненциальной или некоторой...
Ветвление и ограничение - эффективная эвристика для задач поиска, и в Википедии перечислен ряд сложных проблем, где использовались ветвление и привязка. Тем не менее, мне не удалось найти ссылки, позволяющие предположить, что это больше, чем просто «один метод» решения этих проблем. Как ни странно,...
Мне кажется, что специалисты по машинному обучению / интеллектуальному анализу данных знакомы с P и NP, но редко говорят о некоторых более тонких классах сложности (например, NC, BPP или IP) и их последствиях для эффективного анализа данных. Есть ли какой-нибудь обзор работы, выполняющей...
Есть ли проблемы, которые являются NP-полными при использовании евклидовой геометрии, но хорошо определены и разрешимы за полиномиальное время для некоторой неевклидовой...
Поскольку мне интересны парсеры (в основном грамматики выражений парсеров), мне интересно, есть ли какая-то работа, которая дает категорический подход к анализу. Любая ссылка на приложения теории категорий к синтаксическому анализу высоко ценится....
В определении (сильной) управляемости с фиксированными параметрами временная граница является выражением вида где входной экземпляр - ( 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 для каждого...
Мотивация: соавтор редактирует рукопись, и я хотел бы увидеть четкое резюме изменений. Все инструменты, подобные "diff", как правило, бесполезны, если вы одновременно перемещаете текст (например, реорганизуете структуру) и делаете локальные правки. Неужели так сложно понять это правильно?...
Я заинтересован в моделировании объектов, от объектно-ориентированного программирования, в теории зависимых типов. В качестве возможного приложения я хотел бы иметь модель, в которой я могу описать различные функции императивных языков программирования. Я мог найти только одну статью о...
Определение чисел Рамси следующее: Пусть положительное число такого , что каждый граф порядка по крайней мере содержит либо клику на вершину или множество стабильного на вершинах.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 , такого, чтобы...
Наименьшая известная формула для детерминанта имеет размер соответствии с фольклором (или Ран Разу в своей статье « Многолинейные формулы для перманента и детерминанта имеют суперполиномиальный размер» ).NO (журналн )NО(журналN)n^{\mathcal O(\log n)} У вас есть ссылки на это? В частности, что это...
Известно ли, что задача множества вершин обратной связи на неориентированных плоских графах ограниченной степени является трудной?Н