Lista problemów silnie NP-trudnych z danymi liczbowymi

11

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.

np-hardness big-list hamiltonian-paths

— sigal maon
źródło

5

Zadaj sobie pytanie, definiując „zdecydowanie”.

— Tyson Williams

3

Najdłuższa ścieżka jest uogólnieniem ścieżki Hamiltonian Path, więc jest silnie NP-trudna.

— Michael Lampis,

(1) Czy „silnie NP” to literówka dla „silnie NP-twardego”? (2) Nie sądzę, że „możemy zrobić tutaj”.

— Tsuyoshi Ito

zabarwienie tęczy wydaje się być trudne, ale może silnie NP również trudne ...?

— vzn

3

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, c_i)$ dla każdego potrójnego ? $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 .

— Mohammad Al-Turkistany
źródło

0

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ą podzbiorów na . $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$

— Marzio De Biasi
źródło

@domotorp: usunąłem pytanie; tutaj kopiuję / wklejam swój komentarz dotyczący przekształcenia ograniczenia w „... znajduję podzbiór, którego produktem jest kwadratowa liczba wolna większa niż M ...”: „Najpierw pomyśl, że pomnóż każdą liczbę przez inną, bardzo dużą liczbę pierwszą, tak że wszystkie są mniej więcej tego samego rozmiaru. Następnie wybranie liczb N byłoby równoznaczne z uzyskaniem dużego produktu. Nie możemy (jeszcze) wygenerować dużych liczb pierwszych w P, ale w rzeczywistości nie potrzebujemy im - zamiast każdej liczby pierwszej możemy użyć względnych liczb pierwszych bez kwadratów, i te, które możemy wygenerować, obliczając pierwsze wielomianowo wiele liczb pierwszych

— Marzio De Biasi

0

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

— Mohammad Al-Turkistany
źródło

0

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

$NP$ $3$

Mam nadzieję że to pomoże!

— PageWizard
źródło