Osobiście najciekawszym problemem jest dla mnie problem pierwszy:
Problem NP (niedeterministycznie wielomianowy) to 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.
Różnica pomiędzy problemami P i NP polega na tym, że w przypadku P znalezienie rozwiązania ma mieć złożoność wielomianową, podczas gdy dla NP sprawdzenie podanego z zewnątrz rozwiązania ma mieć taką złożoność.
Przykładowo rozważmy problem:
- Czy jakikolwiek niepusty podzbiór zadanego zbioru (np. {-2,6,-3,72,10,-11}) sumuje się do zera ?
Problem jest nierozwiązany. Wielokrotnie przedstawiano próby jej udowodnienia jak i obalenia, a także wykazania niedowodliwości.
Brak komentarzy:
Prześlij komentarz