O co chodzi z tym problem, bo wydaje mi się że rozumiem ale nie jestem pewien. Napisze co mi się wydaje. P oznacza algorytm o z łożonośći wielomianowej. NP oznacza algorytm o złozności nie wielomianowej.
Nie. P zawiera się w NP, więc problemy z rozwiązaniami o złożoności wielomianowej zawierają się zarówno w P jak i NP. Inaczej mówiąc, NP jest nadzbiorem P i to wynika wprost z definicji. Problem polega na tym czy istnieją problemy należące do NP, ale nie należące do P.
ed. Doczytałem trochę i problem NP to taki którego podzbiór można sprawdzić w czasie wielomianowym, ale sam problem ma lub nie ma wiekszą złożoność. Tylko ciągle wydaje mi się to za prostę.Co robie zle?
Wiki mówi tak:
Problem NP (ang. nondeterministic polynomial, niedeterministycznie wielomianowy) – problem decyzyjny, dla którego rozwiązanie można zweryfikować w czasie wielomianowym. Równoważna definicja mówi, że problem jest w klasie NP, jeśli może być rozwiązany w wielomianowym czasie na niedeterministycznej maszynie Turinga.
A więc mamy:
- problem typu P może być rozwiązany w czasie wielomianowym na deterministycznej maszynie Turinga (a co za tym idzie także na niedeterministycznej maszynie Turinga)
- problem typu NP może być rozwiązany w czasie wielomianowym na niedeterministycznej maszynie Turinga
Różnica między deterministyczna, a niedeterministyczną maszyną Turinga jest opisana na Wiki, ale może podam przykład. Weźmy na tapet https://pl.wikipedia.org/wiki/Problem_sumy_podzbioru Rozwiązanie (na potrzeby rozważań) może być takie:
bool sumsToZero(int[] numbers) {
return sumsToZero(numbers, 0, false, 0);
}
bool sumsToZero(int[] numbers, int index, bool nonEmpty, int cumulativeSum) {
if (index == numbers.length) {
return nonEmpty && cumulativeSum == 0;
}
return spawn(() => sumsToZero(numbers, index + 1, nonEmpty, cumulativeSum)) ||
spawn(() => sumsToZero(numbers, index + 1, true, cumulativeSum + numbers[index]));
}
Przy założeniu, że mamy jeden wątek to powyższe rozwiązanie ma złożoność O(2^n) (czyli niewielomianową). Jednak gdy założymy, że mamy dostępną nieskończoną liczbę wątków to powyższe rozwiązanie ma złożoność O(n) (czyli wielomianową). Na tym mniej więcej polega różnica między deterministycznymi a niedeterministycznymi maszynami. W niedeterministycznej maszynie rozwiązującej problem w czasie wielomianowym:
- startujesz z jednym wątkiem (tak jak w deterministycznej maszynie)
- stworzenie dodatkowego wątku zabiera czas O(1) w wątku tworzącym
- dostępnych wątków jest nieskończona ilość (w "praktyce" jest skończona, bo skoro stworzenie nowego wątku zabiera czas, a startujesz z jednym to nie stworzysz nieskończonej liczby wątków w skończonym czasie)
- każdy wątek ma swoją osobną maszynę/ rdzeń/ obojętne, chodzi o to, że stworzenie nowych wątków nie spowalnia wykonywania żadnego z nich
- czas wykonywania każdego z wątków jest wielomianowy (tak jak w deterministycznej maszynie, gdzie jest tylko jeden wątek)