Читая статью «Пора ли объявить победу в подсчете сложностей?» в блоге «Потерянное письмо Годеля и P = NP» они упомянули дихотомию для CSP. После некоторой ссылки, поиска в Google и википедирования, я наткнулся на теорему Ладнера : Теорема Ладнера: если , то в N P ∖ P существуют проблемы , которые...
Даны mmm от nnn двоичной матрицы MMM (записи являются 000 или 111 ), проблема в том , чтобы определить, существует два двоичных векторов v1≠v2v1≠v2v_1 \ne v_2 таким образом, что Mv1=Mv2Mv1=Mv2Mv_1 = Mv_2 (все операции , выполняемые над ZZ\mathbb{Z} ). Эта проблема NP-сложная? Это ясно в NP,...
Является ли следующая проблема NP-трудной? Учитывая конфигурацию доски для n×nn×nn\times n международных шашек , найдите один законный ход. Соответствующая задача для американских шашек (или английских шашек) тривиально разрешима за полиномиальное время. Есть три основных различия между этими двумя...
Рассмотрим задачу покрытия минимального набора со следующими ограничениями: каждый набор содержит не более элементов, а каждый элемент юниверса встречается не более чем в f наборах.kkkfff Пример: случай и f = 2 эквивалентен задаче минимального покрытия вершин в графах с максимальной степенью...
Была ли изучена сложность следующей проблемы? Вход : кубический (или регулярный) граф G = ( V , E ) , естественная верхняя граница t333G=(V,E)G=(V,E)G=(V,E)ttt Вопрос : есть ли раздел на | E | / 3 части размера 3 , так что сумма порядков (необязательно связанных) соответствующих подграфов не...
Есть ли какие-либо ссылки на
Рассмотрим следующую проблему: учитывая формулу CNF и присвоение, которое удовлетворяет этой формуле, есть ли другое удовлетворяющее назначение для этой формулы? В чем сложность этой проблемы? (Это наверняка есть в NP, но это также NP-hard?) Что если вам не дано назначение, и вы просто хотите...
Для любого n>0n>0n > 0 я говорю, что последовательность целых чисел в является -полной, если для каждой перестановки из , записанная как последовательность попарно различных целых чисел , последовательность является подпоследовательностью , т. е. существуеттакой, что для всех .{ 1 , … , n } n...
Известно, что он является NP-полным, чтобы проверить, существует ли гамильтонов цикл в 3-регулярном графе, даже если он плоский (Гэри, Джонсон и Тарьян, SIAM J. Comput. 1976) или двудольный (Akiyama, Nishizeki, и Saito, J. Inform. Proc. 1980), или чтобы проверить, существует ли гамильтонов цикл в...
Существует богатая литература и, по крайней мере, одна очень хорошая книга, в которой излагаются известные значения твердости аппроксимации для NP-трудных задач в контексте мультипликативной ошибки (например, 2-аппроксимация для покрытия вершин оптимальна при условии UGC). Это также включает хорошо...
Существуют ли какие-либо NP-полные задачи, для которых известен алгоритм, согласно которому ожидаемое время выполнения является полиномиальным (для некоторого разумного распределения по экземплярам)? Если нет, то существуют ли проблемы, для которых было установлено существование такого алгоритма?...
Меня интересует проблема упаковки идентичных копий (2-мерных) прямоугольников в выпуклый (2-мерный) многоугольник без перекрытий. В моей задаче вы не можете поворачивать прямоугольники и можете предполагать, что они ориентированы параллельно осям. Вам только что дали размеры прямоугольника и...
Известно, что гамильтонов цикл (для краткости Хэм) NP-полон, а планарный цикл Хэма NP-полон. Доказательство для плоского цикла Хэма не из цикла Хэма. Есть ли хороший гаджет, который с учетом графа G заменит все пересечения некоторым плоским гаджетом, чтобы у вас был планарный граф G 'такой, что G...
Я фиксируем регулярный язык на алфавите , и я считаю следующую проблему , которую я называю письмо планирования для L . Неофициально, ввод дает мне n букв и интервал для каждой буквы (то есть минимальную и максимальную позицию), и моя цель состоит в том, чтобы поместить каждую букву в ее интервал...
При постоянная , можно определить в линейное время, учитывая входной граф G , является ли его древесной шириной есть ≤ K . Однако, когда оба k и G даны в качестве входных данных, проблема NP-трудна. ( Источник ).k ∈ Nk∈Nk \in \mathbb{N}гGG≤ k≤k\leq kКkkгGG Однако, когда входной граф является...
Ясно, что сокращение от CLIQUE до k-Color, потому что они оба NP-Complete. Фактически, я могу построить один, составив сокращение от CLIQUE до 3-SAT с сокращением от 3-SAT до k-Color. Мне интересно, есть ли разумное прямое сокращение между этими проблемами. Скажем, сокращение, которое я мог бы...
Задача «Не все равно kkk -SAT» (NAE kkk -SAT), учитывая набор CCC предложений над набором XXX булевых переменных, так что каждое предложение содержит не более kkk литералов, спрашивает, существует ли истинное присвоение переменных таким образом, чтобы каждое предложение содержит, по крайней мере,...
Этот вопрос связан с ответом, который я разместил в ответ на другой вопрос. Задача с 3 разделами представляет собой следующую проблему: Экземпляр : положительные целые числа a 1 ,…, a n , где n = 3m, а сумма n целых чисел равна mB, так что каждый a i удовлетворяет B / 4 <a i <B / 2. Вопрос :...
Точная формулировка названия принадлежит Ананду Кулькарни (который предложил создать этот сайт). Этот вопрос был задан в качестве примера вопроса, но мне безумно любопытно. Я очень мало знаю об алгебраической геометрии, и на самом деле у меня есть только беглое понимание студентами препятствий,...
Это похоже на « Алгоритмы из Книги ». Хотя сокращения также являются алгоритмами, я подумал, что сомнительно, что можно подумать о сокращении в ответ на вопрос об алгоритмах из книги. Отсюда отдельный запрос! Сокращения всех видов приветствуются. Я начну с действительно простого сокращения от...