Задача разбиения слабо NP-полна, поскольку имеет алгоритм полиномиального (псевдополиномиального) времени, если входные целые числа ограничены каким-либо полиномом. Однако 3-разбиение является сильно NP-полной задачей, даже если входные целые числа ограничены полиномом.
Предполагая, , можем ли мы доказать, что промежуточные NP-полные задачи должны существовать? Если ответ «да», существует ли такая «естественная» проблема кандидата?
Здесь промежуточная NP-полная проблема - это проблема, которая не имеет ни псевдополиномиального алгоритма времени, ни NP-полной в строгом смысле.
Я предполагаю, что существует бесконечная иерархия промежуточных NP-полных задач между слабой NP-полнотой и сильной NP-полнотой.
РЕДАКТИРОВАТЬ 6 марта : Как уже упоминалось в комментариях, альтернативный способ поставить вопрос:
Предполагая, , можем ли мы доказать существование NP-полных задач, которые не имеют ни алгоритма полиномиального времени, ни NP-полных, когда числовые входные данные представлены в унарном виде? Если ответ «да», существует ли такая «естественная» проблема кандидата?
РЕДАКТИРОВАТЬ 2 марта 6 : обратное направление импликации верно. Существование таких "промежуточных" -полных проблемы вытекает , так как если , то одинарные -полных проблемы в .Р ≠ Н Р Р = Н Р Н Р Р
источник
Ответы:
Это частичный ответ, который дает только кандидату промежуточную -полную проблему.Nп
Равная Сумма Поднаборы проблема: Учитывая мультимножество п положительных чисел A = { 1 , . , , , П } , есть к непустые непересекающиеся подмножества S 1 , . , , , S K ⊆ { 1 , . , , , a n } такой, что s u m ( S 1 ) = . , ,К N A = { a1, . , , ,N} К S1, . , , , SК⊆ { а1, . , , ,N} ?s u m ( S1)=...=sum(Sk)
Задача слабо -полна, когда k = O ( 1 ), и поэтому имеет алгоритм псевдополиномиального времени для любого фиксированного постоянного целого числа k > 2 . Однако оно становится сильно N P -полным, когда число подмножеств равной суммы k = Ω ( n ) .NP k=O(1) k>2 NP k=Ω(n)
Если и k = O ( log n ), то задача k -Уравнительных сумм подмножеств является промежуточной N P -полной проблемой-кандидатом (как описано в вопросе). Известно, что эта проблема не имеет алгоритма псевдополиномиального времени и не является N P -полной в строгом смысле.k=ω(1) k=O(logn) k NP NP
Ссылка:
CIELIEBAK, EIDENBENZ, PAGOURTZIS и SCHLUDE, О СЛОЖНОСТИ ВАРИАЦИЙ РАВНЫХ СУБСЕТОВ, Nordic Journal of Computing 14 (2008), 151–172
источник