Lista problemów silnie NP-trudnych z danymi liczbowymi

Szukam silnie trudnych NP problemów dla redukcji. Do tej pory znalazłem następujące problemy:

• Problem z 3 partycjami
• problem z pakowaniem pojemników
• Trójwymiarowe dopasowanie numeryczne
• TSP
• Każdy problem NP-zupełny bez danych liczbowych, np. SATYSFIABILNOŚĆ, CYKL HAMILTONII, 3-KOLOURABILNOŚĆ.

Czy ktoś zna listę problemów o wysokim stopniu NP?

Jeśli nie, zbudujmy tutaj. Czy znasz inne problemy z danymi liczbowymi, które są silnie NP-trudne?

Szczególnie interesują mnie problemy z trudnymi NP na wykresach ważonych.

Oto silnie -Complete$NP$ problemem (z danych liczbowych, jak wymagane):

Problem Schur Triples :

Dane wejściowe: lista 3N różnych dodatnich liczb całkowitych

Pytanie: Czy istnieje podział listy na N trzykrotnie tak, że a i + b i = $(a_i, b_i, c_i)$ dla każdego potrójnego i ?$a_i + b_i= c_i$$i$

Warunek, że wszystkie liczby muszą być odrębne, sprawia, że ​​problem jest bardzo interesujący, a McDiarmid nazywa go zaskakująco kłopotliwym .

Zastanawiając się nad możliwymi odpowiedziami, wpadłem na ten prosty problem numeryczny o silnym uzupełnieniu NP:

BEZPŁATNY PRODUKT SUBSETOWY: Biorąc pod uwagę liczb całkowitych, znajdź $3N$$N$ z nich, których produkt jest kwadratowy.

Szkic próbny: zaczynając od instancji Exact Cover by 3 sets (X3C) (silnie NPC) oznaczaj każdy element wszechświata odrębną liczbą pierwszą (możesz wygenerować z nich w czasie wielomianowym); następnie przekonwertuj każdą potrójną ( x , y , z ) podzbiorów na x y z .$3|X|$$(x,y,z)$$xyz$

Nigdzie go nie znalazłem, więc może być nieco „oryginalny”.

$B$

Można go również trochę zhakować, aby uzyskać inne warianty, takie jak:

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

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

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

$NP$$3$

Mam nadzieję że to pomoże!