Jak mogłoby istnieć rozwiązanie wielomianu czasu dla problemu sum podzbioru?
: 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?