Trudno znaleźć rozwiązanie tego zagadnienia w czasie wielomianowym. Nasuwający się algorytm sprawdzenia wszystkich możliwych podzbiorów ma złożoność wykładniczą ze względu na liczebność zbioru. Nie wiadomo zatem, czy problem ten jest klasy P. Na pewno natomiast uzyskawszy z zewnątrz kandydata na rozwiązanie (np. ) możemy w liniowym (a zatem wielomianowym) czasie sprawdzić, czy sumuje się do zera. Jest to zatem problem NP.
W szczególności wszystkie problemy klasy P są NP, ponieważ można je sprawdzić w czasie wielomianowym. Innymi słowy, klasa P zawiera się nieostro w NP Nie wiadomo natomiast, czy istnieje problem NP, który nie jest w klasie P (czyli, czy P różni się od NP lub inaczej albo ). Jest to jeden z problemów milenijnych.
Prognozy na rozwiązanie Podejmowano kilka prób oszacowania, kiedy ten problem może być rozstrzygnięty: W 2000 roku Buss przewidywał, że zostanie potwierdzone w ciągu 20 lat. W 2001http://www.cs.umd.edu/~gasarch/papers/poll2012.pdf roku 40 spośród 97 ekspertów było przekonanych, że problem ten zostanie rozwiązany do 2039 roku, a 57, że do roku 2070http://www.cs.umd.edu/~gasarch/papers/poll.pdf. Według New Scientist z 2010 roku istnieje 50% szans na rozwiązanie problemu przed 2024 rokiem, gdyż 9 spośród 18 badanych hipotez udowodniono, zanim upłynęły 54 lata od ich postawienia2011 preview: