Список сильно NP-сложных задач с числовыми данными

Я ищу сильно NP-трудные проблемы для сокращения. До сих пор я обнаружил следующие проблемы:

• 3-х секционная задача
• проблема упаковки в мусорное ведро
• Числовое 3-мерное сопоставление
• TSP
• Любая NP-полная задача без числовых данных, например, СООТВЕТСТВИЕ, ГАМИЛЬТОНИЙСКИЙ ЦИКЛ, 3-ЦВЕТНОСТЬ.

Кто-нибудь знает список сильно NP-сложных проблем?

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

Я особенно заинтересован в сильно NP-сложных задачах на взвешенных графах.

Вот сильно -полная$NP$ проблема (с запрошенными вами числовыми данными):

Проблема Шура Триплеса :

Ввод: список из 3N различных положительных чисел

Вопрос: существует ли разбиение списка на N троек , что a i + b i = c i для каждой тройки $(a_i, b_i, c_i)$$a_i + b_i= c_i$$i$ ?

Условие, что все числа должны быть различны, делает проблему очень интересной, и Макдиармид называет ее удивительно неприятной .

Размышляя о возможных ответах, я столкнулся с этой простой числовой сильно NP-полной задачей:

КВАДРАТНЫЙ БЕСПЛАТНЫЙ СУБСЕТНЫЙ ПРОДУКТ: Если дано целых чисел, найдите N из них, произведение которых не содержит квадратов.$3N$$N$

$3|X|$$(x,y,z)$$xyz$ .

Я его нигде не нашел, поэтому он может быть несколько «оригинальным».

$B$ , см. David S. Johnson: Колонка NP-Полноты: Постоянное руководство. 393-405).

Также можно немного взломать, чтобы получить другие варианты, такие как:

• $3N$$N$$21$
• $N$

$k= \Omega(n)$$NP$

$NP$$P||C_{max}$

$NP$$3$

Надеюсь это поможет!