Является ли следующее решение задачи NP-завершенным: Пусть неориентированный граф и двумя целыми числами. Можно ли выбрать для каждой вершины ровно разных соседей, чтобы ни один узел не был выбран больше, чем раз.GGGb≤cb≤cb \le cGGGbbbccc Случай может быть решен для любого за полиномиальное время с...
Как вы можете заставить партию быть честной (подчиняться правилам протокола)? Я видел некоторые механизмы, такие как обязательства, доказательства и т. Д., Но они просто не решают всей проблемы. Мне кажется, что структура дизайна протокола и такие механизмы должны выполнять свою работу. У...
Интересно, есть ли у них какие-либо подходы, формулирующие проблему маршрутизации транспортного средства с временными окнами ( VRPTW ) (как проблему решения) в качестве экземпляра SAT / SMT? (альтернатива: TSP) Например: «Есть ли правильное решение для посещения всех клиентов в пределах их...
Когда я посмотрел « Динамический программный подход к решению задач секвенирования » Майкла Хелда и Ричарда М. Карпа, у меня возник следующий вопрос: почему сложность их алгоритма для TSP равна (∑n−1k=2k(k−1)(n−1k))+(n−1)(∑k=2n−1k(k−1)(n−1k))+(n−1)(\sum_{k=2}^{n-1}k(k-1)\binom{n-1}{k})+(n-1) (стр....
Вкратце: если предположить, что существуют односторонние перестановки , можем ли мы создать такую, которая не имеет люка? Больше информации: Односторонняя перестановка - это перестановка ππ\piкоторый легко вычислить, но трудно инвертировать (см. вики-тег с односторонним действием для более...
В качестве продолжения моего предыдущего вопроса , который был разрешен Сянь-Чжи Чангом, приведу еще одну попытку найти соответствующее обобщение теоремы Рамсея. (Вам не нужно читать предыдущий вопрос; этот пост является самостоятельным.) Параметры: целые числа 1≪d≪k≪n1≪d≪k≪n1 \ll d \ll k \ll n...
Позволять ВVV быть набором DDDпрямоугольные формы. Заd∈ { 1 , . , , , D }d∈{1,...,D}d \in \{1,...,D\} а также v ∈ Vv∈Vv \in V, wd(v)∈Q+wd(v)∈Q+w_d(v) \in \mathbb{Q}^{+} описывает длину vvv в измерении ddd, То же обозначение используется для контейнераCCC, DDDзадача об ортогональной упаковке...
Для проекта, над которым я работаю, я должен генерировать случайные остовные деревья с ограниченной высотой. В основном я делаю следующее: 1) Создаю связующее дерево. 2) Проверяю осуществимость, если возможно, сохраняю его. 1) Начиная с минимального связующего дерева (Прима или Крускала), я...
Мне было трудно найти алгоритм или опубликовать статьи о триангуляции самопересекающегося многоугольника (также многоугольника со структурой дырок). Может, кто-нибудь поможет мне найти опубликованную статью / алгоритм, пожалуйста? PS: кто-то пометит этот вопрос соответствующим образом, пожалуйста,...
Я хотел бы знать, куда я могу обратиться за хорошим, мягким введением в k-SAT (это может быть для математиков, которые могут не иметь хорошего компьютерного фона). Я также хотел бы знать статьи, которые, возможно, опрашивают или объясняют текущие методы, используемые для решения k-SAT. Наконец,...
Я имею в виду вопрос здесь: мощные алгоритмы слишком сложны для реализации . Если алгоритм является мощным, но слишком сложным для реализации, как вы можете быть уверены, что алгоритм правильный? Без реализации вы не сможете протестировать алгоритм в реальном сценарии, и такой сложный алгоритм...
По моему опыту, контекстно-зависимые языки и линейно-ограниченные автоматы часто пропускаются или зацикливаются на курсах теории вычислимости, и даже не учтены в некоторых заметных учебниках, хотя конечным автоматам и автоматам с выталкивающими функциями уделяется много внимания. Конечно, должна...
Этот пост отделен от Последствия UP равно NP , а также является дополнительным вопросом к классам семантической и синтаксической сложности . В вышеприведенном посте мы узнали о семантических и синтаксических классах. Вкратце, если класс можно охарактеризовать как листовой класс языка , то класс...
недавно Крэйг Джентри опубликовал первую схему шифрования с открытым ключом (через открытый текст {0,1}), которая полностью гомоморфна, что означает, что можно эффективно и компактно оценивать AND и XOR на зашифрованных открытых текстах без знания секретного ключа дешифрования. Мне интересно, есть...
Хорошо известными примерами вычислений, вдохновленных природными явлениями, являются квантовые компьютеры и компьютеры с ДНК. Что известно о потенциале и / или ограничениях вычислений по законам Максвелла или гравитации? То есть непосредственное включение природных «быстрых» решений уравнений...
Как вы все знаете, из-за финансового кризиса 2008 года продолжаются последствия. Я думал о том, как теория сложности вписывается во все это, когда я понял, что не знаю базовых классов сложности, связанных с финансовой экономикой. Поэтому мой вопрос заключается в том, какова классификация сложности...
Есть ли перестановки π1,π2π1,π2\pi_1,\pi_2 и полиномиальный размер (в |w|=n|w|=n|w|=n) контекстно-бесплатная грамматика, описывающая конечный язык {wπ1(w)π2(w)}{wπ1(w)π2(w)}\{w \pi_1(w) \pi_2(w)\} по алфавиту {0,1}{0,1}\{0,1\}? ОБНОВЛЕНИЕ: для одной перестановки ππ\pi это возможно. ππ\pi является...
Теорема Фари говорит, что простой планарный граф можно нарисовать без пересечений, так что каждое ребро является отрезком прямой. Мой вопрос заключается в том, существует ли аналогичная теорема для графов ограниченного числа пересечений . В частности, можем ли мы сказать, что простой график с...
В сложности дерева решений для булевой функции очень хорошо известный метод нижней границы состоит в том, чтобы найти (приблизительный) многочлен, который представляет функцию. Патури дал характеристику для симметричных булевых (частичных и полных) функций в терминах величины, обозначаемой...
Этот вопрос возник в контексте криптографии, но ниже я представлю его с точки зрения теории сложности, поскольку здесь люди больше знакомы с последним. Этот вопрос связан с проблемами в NP, но не в Average-P / poly и неоднородности биения по Oracle Access . Неформальное утверждение: когда...