Задача о гамильтоновом цикле (HC) состоит в том, чтобы найти цикл, который проходит через все вершины в данном неориентированном графе. Задача коммивояжера (TSP) состоит в том, чтобы найти цикл, который проходит через все вершины в данном графе, взвешенном по ребрам, и минимизирует общее...
Пока пишу небольшой пост о сложности видеоигр Nibbler и Snake ; Я обнаружил, что они оба могут быть смоделированы как задачи реконфигурации на плоских графах; и кажется маловероятным, что такие проблемы не были хорошо изучены в области планирования движения (представьте, например, цепочку связанных...
Вот проблема: У нас есть квадрат с несколькими числами от 1..N в некоторых ячейках. Нужно определить, можно ли его завершить до магического квадрата. Примеры: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _ Эта проблема NP-полная? Если да, как я могу это...
Учитывая конечный (детерминированный или недетерминированный, я не думаю, что это имеет большое значение) автомат A и порог n , принимает ли A слово, содержащее не более n различных букв? (Под k разными буквами я подразумеваю, что aabaa имеет две разные буквы, a и b .) Я показал, что эта задача...
Насколько сложно найти самое редкое решение системы линейных уравнений? Более формально рассмотрим следующую проблему решения: Экземпляр: система линейных уравнений с целыми коэффициентами и числом ccc . Вопрос: существует ли решение для системы с хотя бы ccc переменными, присвоенными нулю? Я также...
Меня интересует сложность задачи о доминирующем множестве (DSP) в некоторых конкретных классах графов, которые являются подклассами хордовых графов . Граф является неориентированным графом путей, если он является графом пересечения вершин семейства путей в некотором неориентированном дереве. Пусть...
Один из моих друзей спрашивает меня о следующей проблеме планирования на дереве. Я считаю, что это очень чисто и интересно. Есть ли какая-либо ссылка на это? Проблема: Существует дерево , каждое ребро имеет симметричную стоимость перемещения 1 . Для каждой вершины v i есть задача, которую...
Известно ли, что задача множества вершин обратной связи на неориентированных плоских графах ограниченной степени является трудной?Н
Может ли кто-нибудь перечислить некоторые известные проблемы, удовлетворяющие следующим условиям: 1. has a generalization problem that is known to be NP-complete 2. has not been proved to be NP-complete nor has a known polynomial time solution....
Treewith является важным параметром графа, который указывает, насколько близко граф от дерева (хотя и не в строгом топологическом смысле). Хорошо известно, что вычисление ширины дерева является NP-сложным. Существуют ли естественные классы графов, для которых сложно вычислить ширину дерева? Так же:...
Некоторое время назад я опубликовал справочный запрос для задач с графами, где мы хотим найти 2-секционное ребро, в котором оба набора удовлетворяют свойству, не связанному с их количеством элементов. Я пытался доказать, что следующая проблема NP-трудна: Для турнира существует ли множество дуг...
Задача разбиения слабо NP-полна, поскольку имеет алгоритм полиномиального (псевдополиномиального) времени, если входные целые числа ограничены каким-либо полиномом. Однако 3-разбиение является сильно NP-полной задачей, даже если входные целые числа ограничены полиномом. Предполагая, , можем ли мы...
Рассмотрим проблему, когда нам задают в качестве входных данных направленный ациклический граф G=(V,E)G=(V,E)G = (V, E) , функцию маркировки λλ\lambda из VVV в некоторый набор LLL с полным порядком...
Рассмотрим следующую проблему. Вход: неориентированный граф . Вывод: граф H, который является младшим из G с самой высокой граничной плотностью среди всех миноров G , то есть с самым высоким отношением | E ( H ) | / | V ( H ) | ,G=(V,E)G=(V,E)G=(V,E)HHHGGGGGG|E(H)|/|V(H)||E(H)|/|V(H)||E(H)|/|V(H)|...
Отвечая на этот вопрос о теории , я (неформально) на лету доказал следующую теорему: Теорема : Для любого фиксированного пробел гамильтонова цикла остается NP-полным, даже если он ограничен планарными двудольными неориентированными графами максимальной степени 3, которые не содержат циклов длины ≤...
Ширина дерева показывает, насколько близок график к дереву. Несколько NP-трудных задач можно решить на графах с ограниченной шириной дерева. Если проблема остается NP-трудной на деревьях, то ширина дерева не может нас спасти. Это было мотивом одного из моих предыдущих вопросов, в котором задавались...
Этот вопрос похож на NP-сложные задачи на деревьях : Существует большое количество NP-полных задач, которые можно отследить на рефератах . Есть ли какие-либо известные проблемы, которые остаются NP-полными, если они ограничены Cographs? Чтобы быть более точным, меня интересуют примеры, в которых...
Рассмотрим следующую проблему: Учитывая набор из положительных чисел { a 1 , … , a n }, в которых k ≥ 3 является константой, мы хотим разбить набор на m подмножеств размера k так, чтобы произведение суммы каждого подмножества максимальноn=kmn=kmn = k m{a1,…,an}{a1,…,an}\{ a_1, \dots, a_n \}k≥3k≥3k...
Судоку - это хорошо известная головоломка, которая является NP-полной. Двоичный судоку - это вариант, который допускает только цифры и 1 . Правила следующие.000111 Каждая строка и каждый столбец должны содержать одинаковое количество нулей и единиц. Каждая строка и каждый столбец уникальны. Ни одна...
Этот вопрос мотивирован этим постом, Можете ли вы определить сумму двух перестановок за полиномиальное время? и мой интерес к вычислительным свойствам перестановок. Разностная последовательность перестановки чисел формируется путем нахождения разности между каждыми двумя соседними числами в...