Промежуточные -полные проблемы?

13

Задача разбиения слабо NP-полна, поскольку имеет алгоритм полиномиального (псевдополиномиального) времени, если входные целые числа ограничены каким-либо полиномом. Однако 3-разбиение является сильно NP-полной задачей, даже если входные целые числа ограничены полиномом.

Предполагая, , можем ли мы доказать, что промежуточные NP-полные задачи должны существовать? Если ответ «да», существует ли такая «естественная» проблема кандидата?пNп

Здесь промежуточная NP-полная проблема - это проблема, которая не имеет ни псевдополиномиального алгоритма времени, ни NP-полной в строгом смысле.

Я предполагаю, что существует бесконечная иерархия промежуточных NP-полных задач между слабой NP-полнотой и сильной NP-полнотой.

РЕДАКТИРОВАТЬ 6 марта : Как уже упоминалось в комментариях, альтернативный способ поставить вопрос:

Предполагая, , можем ли мы доказать существование NP-полных задач, которые не имеют ни алгоритма полиномиального времени, ни NP-полных, когда числовые входные данные представлены в унарном виде? Если ответ «да», существует ли такая «естественная» проблема кандидата?пNп

РЕДАКТИРОВАТЬ 2 марта 6 : обратное направление импликации верно. Существование таких "промежуточных" -полных проблемы вытекает , так как если , то одинарные -полных проблемы в .Р Н Р Р = Н Р Н Р РNпPNPP=NPNPP

Мухаммед Аль-Туркистани
источник
2
@MarzioDeBiasi Существует еще одно определение сильной NP-полноты (может быть, менее популярное), которое определяет числовую задачу для NP-полноты, даже если все входные целые числа представлены в унарной записи.
Мухаммед Аль-Туркистани
4
@vzn это смешной комментарий! 1) Лэднерс thm не о сложных проблемах, которые не являются законченными; 2) в то время как Мухаммед является своего рода перегрузочной терминологией, он четко определяет свой класс проблем (NPC, не сильно NPC и не алгоритм псевдополии времени), и он отличается от NPC.
Сашо Николов
2
@ MohammadAl-Turkistany: хорошо, спасибо, возможно, я предлагаю вам назвать это унарной NP-полнотой, как у Гэри и Джонсона "Сильные" NP- полноты. Результаты: мотивация, примеры и последствия . Итак, вы ищете промежуточные проблемы между унарным NPC и псевдополиномиальным NPC. Я все еще пытаюсь понять это, однако, в своей статье G & J говорит (об унарном NPC): «... Нетрудно понять, что это соответствует нашему представлению о сильной NP-полноте ...».
Марцио Де Биаси
2
@MarzioDeBiasi Я думаю, что идея заключается в том, что мы можем (->) задавать двоичное число многочлена размера на входе, преобразовывать его в унарный в polytime и запускать унарный алгоритм, (<-), учитывая унарный ввод длины poly в Остальные входные данные, прочитайте все это и преобразуйте его в двоичный файл и запустите двоичный алгоритм.
Усул
1
Поскольку любая проблема, имеющая алгоритм полиномиального времени, если один из входных параметров является фиксированным, относится к FPT, вы, по-видимому, по существу спрашиваете, существуют ли проблемы сложнее, чем FPT, но не W [1] -hard. Насколько я знаю, теорема Ладнера может быть расширена до этой установки; это может быть в учебнике Flum / Grohe.
Андрас Саламон

Ответы:

2

Это частичный ответ, который дает только кандидату промежуточную -полную проблему.Nп

Равная Сумма Поднаборы проблема: Учитывая мультимножество п положительных чисел A = { 1 , . , , , П } , есть к непустые непересекающиеся подмножества S 1 , . , , , S K{ 1 , . , , , a n } такой, что s u m ( S 1 ) = . , ,КNAзнак равно{a1,,,,,aN}КS1,,,,,SК{a1,,,,,aN} ?sum(S1)=...=sum(Sk)

Задача слабо -полна, когда k = O ( 1 ), и поэтому имеет алгоритм псевдополиномиального времени для любого фиксированного постоянного целого числа k > 2 . Однако оно становится сильно N P -полным, когда число подмножеств равной суммы k = Ω ( n ) .NPk=O(1)k>2NPk=Ω(n)

Если и k = O ( log n ), то задача k -Уравнительных сумм подмножеств является промежуточной N P -полной проблемой-кандидатом (как описано в вопросе). Известно, что эта проблема не имеет алгоритма псевдополиномиального времени и не является N P -полной в строгом смысле.k=ω(1)k=O(logn)kNPNP

Ссылка:

CIELIEBAK, EIDENBENZ, PAGOURTZIS и SCHLUDE, О СЛОЖНОСТИ ВАРИАЦИЙ РАВНЫХ СУБСЕТОВ, Nordic Journal of Computing 14 (2008), 151–172

Мухаммед Аль-Туркистани
источник
Вы видели этот cstheory.stackexchange.com/a/7427/15637 ?
Томас Калиновский
Да. Этот ответ дает, вероятно, искусственную проблему.
Мухаммед Аль-Туркистани