Насколько сложна проблема Set Cover, если число элементов ограничено некоторой функцией (например, ), где - размер экземпляра задачи. Формально,n
Пусть и где и . Насколько сложно решить следующую проблему?F = { S 1 , ⋯ , S n } S i ⊆ U m = O ( log n )
Что если ?
Любой результат, основанный на общеизвестных догадках (например, Unique Games, ETH), хорош.
Редактировать 1: Мотивация для этой проблемы заключается в том, чтобы выяснить, когда проблема усугубляется с увеличением . Ясно, что проблема в P, если и NP-hard, если . Какой порог для NP-сложности проблемы?m = O ( 1 ) m = O ( n )
Редактировать 2: Существует тривиальный алгоритм для его решения за время (который перечисляет все подмножества размера в ). Следовательно, задача не является NP-сложной, если поскольку ETH подразумевает, что не существует алгоритма во времени для любой NP-сложной задачи. проблема (где - размер NP-сложной задачи).m F m = O ( log n ) O ( 2 n o ( 1 ) ) n
источник
Ответы:
Когда , вы можете использовать динамическое программирование, чтобы найти оптимальное за полиномиальное время. Таблица содержит булевозначные ячейки для каждого и , указывающие, существуют ли наборы, которые покрывают элементов в .T ℓ , X ℓ ∈ { 0 , … , k } X ⊆ U ℓ Xm = O ( logн ) Tℓ , X ℓ ∈ { 0 , … , k } Икс⊆U ℓ X
Когда , скажем, , проблема остается NP-трудной. Для данного экземпляра SET-COVER добавьте новых элементов и новых набора, состоящих из непустых подмножеств новых элементов, включая (когда достаточно велико, ). Также увеличьте на единицу. Новые - это и .m≤C √m=O(n−−√) mx1,…,xm(2C - 1 м)2{x1,…,xm}m(2C - 1 м)2<2mkm,nm′=2mn′=n+(2C - 1 м)2≥m≤Cn−−√ m x1,…,xm (2C−1m)2 {x1,…,xm} m (2C−1m)2<2m k м , н м'= 2 м N'= n + ( 2 C- 1м )2≥ ( C- 1м')2
источник
Случай находится в времени, как отметил Ювал, но также обратите внимание, что для вы можете решить проблему в время (полиномиальное время) путем исчерпывающего поиска. Предполагая гипотезу сильного экспоненциального времени (что для CNF-SAT по формулам с переменными и предложениями требуется как минимум времени), эти две временные границы являются «пределом» того, что мы можем ожидать в полиномиальное время, в следующем смысле.n O ( c ) k = O ( 1 ) O ( n k ⋅ m ) N O ( N ) 2 N - o ( N )m=clogn nO(c) k=O(1) O(nk⋅m) N O(N) 2N−o(N)
В моей статье SODA'10 с Михаем Патраску мы изучаем существенно изоморфную проблему нахождения доминирующего множества размера в произвольном узловом графе, показывая, что если доминирующее множество можно решить в время для некоторого и , тогда существует временной алгоритм для CNF-SAT для переменных и предложений.n k n k - εk n k nk−ε ε > 0 2 N ( 1 - ε / 2 ) p o l y ( M ) N Mk≥2 ε>0 2N(1−ε/2)poly(M) N M
Отметив взаимосвязь между окрестностями вершин в экземпляре доминирующего набора и множествами в экземпляре покрытия набора, и изучив редукцию, вы обнаружите, что это сокращение также показывает решение -Set Cover с наборами в юниверсе размера в Время подразумевает алгоритм CNF-SAT для формул CNF с предложениями и переменными, работающими за времени , Для опровержения Сильного ETH достаточно решить CNF-SAT в случае, когда . Следовательно, алгоритм для вашей задачи работает вn m n k - ε ⋅ f ( m ) M N 2 N ( 1 - ε / 2 ) ⋅ f ( M ) M = O ( N ) n k - ε ⋅ 2 m / α ( m ) α ( m )k n m nk−ε⋅f(m) M N 2N(1−ε/2)⋅f(M) M=O(N) nk−ε⋅2m/α(m) Время для некоторой неограниченной функции привело бы к неожиданному новому алгоритму SAT.α(m)
источник