Numeryczne dopasowanie trójwymiarowe
Numeryczne dopasowywanie trójwymiarowe jest problemem decyzyjnym NP-zupełnym . Jest to podane przez trzy liczb całkowitych , Y { , z których każdy zawiera elementy i . wybranie X tak, że każda liczba całkowita w , i występuje dokładnie raz i że dla każdej potrójnej w podzbiorze posiada. Ten problem jest oznaczony jako [SP16] w.
Przykład
Weź , Z i . Ta instancja ma rozwiązanie, a mianowicie . Zauważ, że każda potrójna suma wynosi . zbiór nie jest rozwiązaniem z kilku powodów: nie każda liczba jest używany (a ), liczba jest używana zbyt często ( ) i nie każda potrójna suma (ponieważ ). Istnieje jednak co najmniej jedno rozwiązanie tego problemu, którym jest interesująca nas właściwość przy problemach decyzyjnych. Gdybyśmy wzięli tego samego ten problem rozwiązania (wszystkie liczby sumują się , co nie jest równe w tym przypadku).
Powiązane problemy
Każde wystąpienie numerycznego problemu dopasowywania trójwymiarowego jest wystąpieniem zarówno problemu z trójwymiarowym podziałem , jak i trójwymiarowego problemu z dopasowywaniem.
Dowód NP-zupełności
NP-zupełność problemu 3-partycji została opisana przez Gareya i Johnsona w „Computers and Intractability; A Guide to the Theory of NP-Completeness”, która odnosi się do tego problemu za pomocą kodu [SP16]. Odbywa się to poprzez redukcję dopasowania 3-wymiarowego poprzez 4-partycję. Aby udowodnić NP-zupełność numerycznego dopasowania 3-wymiarowego, dowód jest podobny, ale należy zastosować redukcję z dopasowania 3-wymiarowego poprzez numeryczny problem dopasowania 4-wymiarowego.