Вопросы с тегом «np-hardness»

15
Срок действия возведения в степень при полиномиальном сокращении времени

Я задал этот вопрос 10 дней назад на cs.stackexchange здесь, но у меня не было никакого ответа. В очень известной статье (в сетевом сообществе) Wang & Crowcroft представили некоторые результаты полноты вычисления пути при нескольких аддитивных / мультипликативных ограничениях. Первая проблема...

15
Bob's Sale (изменение порядка пар с ограничениями для минимизации суммы продуктов)

Я задал этот вопрос о переполнении стека некоторое время назад: Проблема: продажа Боба . Кто-то предложил также разместить здесь вопрос. Кто-то уже задавал вопрос, связанный с этой проблемой, здесь - минимальный вес леса данной мощности - но, насколько я понимаю, это не помогает мне с моей...

15
Ударять множество попарно пересекающихся семейств

Наезд набор из семейства является подмножеством из такое , что для . Задача найти минимальное множество попаданий данного семейства NP-трудна в общем, поскольку она обобщает проблему покрытия вершин. Теперь мой вопрос:S= { S1, … , SN}Sзнак равно{S1,...,SN}\mathcal{S} = \{S_1, \dots, S_n\}ЧАСЧАСH⋃Nя...

15
Сумма подмножества против продукта подмножества (сильная или слабая твердость NP)

Я надеялся, что кто-нибудь сможет объяснить мне, почему именно проблема подмножеств является сильно NP-трудной, в то время как проблема сумм подмножеств является NP-трудной. Подмножество Сумма: Дано и Т , существует ли подмножество X ' такое , что Σ я ∈ Х ' х я = Т .Икс= { х1, . , , ,...

15
Ранжирование сложности сложных задач на практике

Этот вопрос тесно связан с другим постом: Фазовые переходы в NP Трудные проблемы, но он несколько иной. В то время как этот вопрос касается сложности отдельных случаев сложных проблем NP, речь идет о ранжировании сложности тех же случаев. Существует много библиографии об эффекте, известном как...

15
Можно ли эффективно равномерно выбрать соседа вершины в графе многогранника?

У меня есть многогранник определенный как .PPP{x:Ax≤b,x≥0}{x:Ax≤b,x≥0}\{ x : Ax \leq b, x \geq 0\} Вопрос: Учитывая вершину из P , есть ли алгоритм полиномиального времени для равномерной выборки из соседей v в графе P ? (Многочлен в измерении, число уравнений и представление б . Я могу...

15
Две матрицы, связанные перестановкой

Какова вычислительная сложность следующей задачи: с учетом двух комплексных матриц A и B проверить, есть ли матрица перестановок Р таким образом, что: В = Р Р Т .n × nN×Nn\times nAAAВВBппPB = PА ПT,Взнак равнопAпT,B = P A P^T. Если это помогает, можно предположить, что и B эрмитовы (или даже что A...

15
Сложна ли следующая проблема NP?

Рассмотрим набор множеств над базовым множеством где и , и пусть будет положительным целым числом.F = { F 1 , F 2 , … , F n } U = { e 1 , e 2 , … , e n } | F i | « П е я ∈ F я кF={F1,F2,…,Fn}F=\{F_1,F_2,\dotsc,F_n\}U={e1,e2,…,en}U=\{e_1,e_2,\dotsc,e_n\}|Fi||F_i| ≪\ll nnei∈Fie_i \in F_ikk Цель...

14
Обнаружение целочисленных отношений для Подмножества Сумм или АЭС?

Есть ли способ закодировать экземпляр суммы подмножества или проблему разбиения числа так, чтобы (небольшое) решение целочисленного отношения дало ответ? Если не точно, то в каком-то вероятностном смысле? Я знаю, что LLL (и, возможно, PSLQ) использовались с умеренным успехом в решении задач Subset...

14
Выборка равномерно случайного удовлетворяющего задания

Проблема: Учитывая представленный булевой схемой, генерируем равномерно случайный x ∈ { 0 , 1 } n такой, что ϕ ( x ) = 1 (или выводим ⊥, если таких нет х существует). ϕ : { 0 , 1 }N→ { 0 , 1 }φ:{0,1}N→{0,1}\phi : \{0,1\}^n \to \{0,1\}x ∈ { 0 , 1 }NИкс∈{0,1}Nx \in \{0,1\}^nϕ ( x ) = 1φ(Икс)знак...

14
Как проблема может быть в NP, быть NP-сложной, а не NP-полной?

Долгое время я думал, что задача была NP-полной, если она (1) NP-сложная и (2) в NP. Однако в известной статье «Метод эллипсоидов и его последствия в комбинаторной оптимизации» авторы утверждают, что проблема дробного хроматического числа принадлежит NP и является NP-сложной, но пока неизвестно,...

14
Является ли задача «Меньше всего отличающихся битов» NP-полной?

Это имя, которое я сделал для этой проблемы. Я не видел нигде описанного ранее. Я пока не смог найти ни доказательства NP-полноты, ни алгоритма полиномиального времени для этой задачи. Это не проблема домашней работы - это связано с проблемой, с которой я столкнулся в своей работе. НАИБОЛЕЕ...

14
Является ли eta-эквивалентность для функций совместимой с операцией seke в Haskell?

Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...

14
NP-Complete задачи, которые допускают эффективный алгоритм под обещанием уникального решения

Недавно я читал очень хорошую статью от Valiant и Vazirani, в которой показано, что если , то не может быть эффективного алгоритма для решения SAT, даже при условии, что он либо неудовлетворителен, либо имеет уникальное решение. , Таким образом, показывая, что SAT не допускает эффективного...

14
Добавьте соответствие к гамильтонову пути, чтобы уменьшить максимальное расстояние между заданными парами вершин

Какова сложность следующей проблемы? Вход : гамильтонов путьв К пHHHKnКNK_n R⊆[n]2р⊆[N]2R \subseteq [n]^2 подмножество пар вершин положительное целое число kКk Запрос : существует ли сопоставление MMM такое, что для каждого (v,u)∈R(v,U)∈р(v,u) \in R , dG(v,u)≤kdграмм(v,U)≤Кd_G(v,u) \leq k ? (где...

14
Точные алгоритмы для r-доминирующего множества на графах ограниченной ширины

Учитывая график, , я хочу , чтобы найти оптимальный г -domination для G . То есть, я хочу подмножество S из V таким образом, что все вершины в G находятся на расстоянии не более чем г от некоторой вершины в S , при сведении к минимуму размера S .G=(V,E)G=(V,E)G = (V, E)rrrGGGSSSVVVGGGrrrSSSSSS Из...

14
Какова минимальная необходимая глубина снижения NP-твердости SAT?

Как все знают, SAT завершен для сравнению с многозначным сокращением за полиномиальное время. Это все еще полные сокращения wrt много-один.NPNP\mathsf{NP}AC0AC0\mathsf{AC^0} Мои вопросы: какова минимальная необходимая глубина для сокращений? Более формально, Что наименьшее такое, что SAT - это...

13
Нахождение разреженного решения системы линейных уравнений

Насколько сложно найти самое редкое решение системы линейных уравнений? Более формально рассмотрим следующую проблему решения: Экземпляр: система линейных уравнений с целыми коэффициентами и числом ccc . Вопрос: существует ли решение для системы с хотя бы ccc переменными, присвоенными нулю? Я также...

13
Является ли задача о половинном магическом квадрате NP-полной?

Вот проблема: У нас есть квадрат с несколькими числами от 1..N в некоторых ячейках. Нужно определить, можно ли его завершить до магического квадрата. Примеры: 2 _ 6 2 7 6 _ 5 1 >>> 9 5 1 4 3 _ 4 3 8 7 _ _ 9 _ _ >>> NO SOLUTION 8 _ _ Эта проблема NP-полная? Если да, как я могу это...

13
Сложные проблемы расширения

В проблеме расширяемости нам дают часть решения, и мы хотим решить, можем ли мы расширить ее до полного решения. Некоторые проблемы расширяемости эффективно разрешимы, в то время как другие проблемы расширяемости превращают легкую проблему в сложную. Например, теорема Кенига-Холла утверждает, что...