Я знаю, что максимальное независимое множество на кубических графах без треугольников является NP-полным. Является ли он еще NP-полным, если нам требуется, чтобы независимый набор имел размер точно ?|V|/2|V|/2|V|/2 В основном, ДА экземпляр задачи о независимом множестве в задаче о кубах без...
Рассмотрим следующую постановку задачи: Получив начальное число, вы и ваш друг по очереди вычитаете из него идеальный квадрат. Первый, кто доберется до нуля, побеждает. Например: Начальное состояние: 37 Игрок1 вычитает 16. Состояние: 21 Игрок2 вычитает 8. Состояние: 13 Игрок1 вычитает 4. Состояние:...
Pebbling - это пасьянс, в который играют на неориентированном графе , где каждая вершина имеет ноль или более камешков. Один шаг гальки состоит из удаления двух камешков из вершины и добавления одного камешка к произвольному соседу . (Очевидно, что у вершины v должно быть как минимум два камешка...
Моя книга утверждает это Если задача решения B находится в P, а A сводится к B, то проблема решения A находится в P. Решение задачи B является NP-полным, если B находится в NP, и для каждой задачи в A в NP, A сводится к B. Решающая задача C является NP-полной, если C находится в NP, а для некоторой...
Рассмотрим следующую проблему, входной экземпляр которой представляет собой простой граф и натуральное целое число k .гGGКkk Существует ли множество такое, что G - S двудольный и | S | ≤ к ?S⊆ V( G )S⊆V(G)S \subseteq V(G)G - SG−SG - S| S| ≤k|S|≤k|S| \leq k Я хотел бы показать, что эта проблема...
У нас было несколько вопросов о связи сокращений Кука и Карпа . Понятно, что сокращения Кука (сокращения Тьюринга за полиномиальное время) не определяют то же понятие NP-полноты, что и сокращения Карпа (сокращения многозначного за полиномиальное время), которые обычно используются. В частности,...
На самом деле я обнаружил, что набор контекстно-зависимых языков, ( принятых языков) не так широко обсуждается, как (обычные языки) или (контекстно-свободные языки). А также открытая проблема не так известна, как «аналогичная» проблема: « ".CSLCSL\mathbf{CSL}R E G C F L D S P A C E ( O ( n ) ) = ?...
Альтернативная формулировка Я придумал альтернативную формулировку нижеприведенной проблемы. Альтернативная формулировка на самом деле является частным случаем проблемы ниже и использует двудольные графы для описания проблемы. Тем не менее, я считаю, что альтернативная формулировка все еще...
Для заданных чисел таких что , существует ли присвоение чисел который является перестановкой такой, чтоA 1 ≤ A 2 ≤ . , , ≤ к к Σ я = 1 А я = K ( 2 K + 1 ) я 1 , я 2 , . , , , Я 2 к 1 , 2 , . , , , 2 кkkkA1≤A2≤...≤AkA1≤A2≤...≤AkA_1 \leq A_2 \leq ... \leq...
У меня проблема в голове, я думаю, что это проблема NPC, но я не знаю, как это доказать. Вот проблема: В очень большом озере k островов и n понтонов в форме вееров. Эти понтоны имеют одинаковый размер, но имеют разные начальные направления и находятся в разных первоначальных положениях в озере....
Существует классическая игра-головоломка, очень похожая на кроссворд, за исключением того, что дается список слов, а затем дается квадратная доска составленная из единичных квадратов, с некоторыми квадратами, затемненными как кроссворд , и на некоторых квадратах уже написано письмо. Цель состоит в...
Я беру курс по вычислительной сложности. Моя проблема в том, что я не понимаю метод релятивизации . К сожалению, во многих учебниках я пытался найти немного интуиции, но пока безуспешно. Буду признателен, если кто-нибудь сможет пролить свет на эту тему, чтобы я смог продолжить сам. Несколько...
Дана (двоичная) целочисленная программа вида:0,10,10,1 mins.t.f(x)Ax=bxi≥0xi∈{0,1}∀i∀iminf(x)s.t.Ax=bxi≥0∀ixi∈{0,1}∀i \begin{array}{lll} \text{min} & f(x) & \\ \text{s.t.} & A x = b \\ & x_i \ge 0 & \quad \forall i\\ & x_i \in \{0,1\} & \quad \forall i \end{array} Обратите внимание, что размер не...
Допустим, мы знаем, что проблема A сложная, затем мы сводим A к неизвестной проблеме B, чтобы доказать, что B также сложно. В качестве примера: мы знаем, что 3-окраска сложна. Затем мы уменьшаем 3-окраску до 4-окраски. Сочетая один из цветов в 3-х раскрасках, вы получаете 4-х раскраски, поэтому...