Jak mogłoby istnieć rozwiązanie wielomianu czasu dla problemu sum podzbioru?

Zbiory, relacje, logika
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
ehangeto4
Witam na forum
Witam na forum
Posty: 1
Rejestracja: 21 wrz 2020, 10:00
Płeć:

Jak mogłoby istnieć rozwiązanie wielomianu czasu dla problemu sum podzbioru?

Post autor: ehangeto4 » 21 wrz 2020, 10:05

Dla zbioru {a} istnieje dokładnie jeden niepusty podzbiór, który może sumować się do zera, a mianowicie {a}. Więc jedynym logicznym sposobem jest to, że a == 0. Jeśli weźmiemy pod uwagę zbiór {a, b}, istnieją trzy scenariusze, które mogą dać nam rozwiązanie: a == 0, b == 0 i b == -a. Jeśli weźmiemy pod uwagę zbiór {a, b, c}, mamy te trzy scenariusze plus c == 0, c == -a, c == -b ic == - (a + b). Łatwo zauważyć i zrozumieć, że liczba scenariuszy do sprawdzenia rośnie wykładniczo do 2 ^ n - 1, gdzie n to liczba elementów w pierwotnym zbiorze. Jak więc mogłoby istnieć rozwiązanie wielomianu czasu dla problemu sum podzbioru?