Na jakim poziomie jesteś obecnie? Zadałeś pytanie z działu złożoności obliczeniowej. To jest znacznie trudniejszy dział infomratyki niż algorytmika.
https://pl.wikipedia.org/wiki/Z%C5%82o%C5%BCono%C5%9B%C4%87_obliczeniowa
[
Stosujemy też szersze pojęcia takie jak klasa P, czy NP mając odpowiednio na uwadze decyzyjne problemy wielomianowe i decyzyjne problemy podlegające wielomianowej weryfikacji, jeśli odpowiedź jest twierdząca.
]
Tu link do chyba najbardziej klasycznego przypadku:
https://pl.wikipedia.org/wiki/Problem_spe%C5%82nialno%C5%9Bci
Pisząc kolokwialnie, jak masz zestaw wartościowania zmiennych to możesz szybko (w czasie P - polynomial,wielomianowym) sprawdzić czy to wartościowanie spełnia czy nie spełnia daną formułę. Natomiast gdy nie masz i musisz szukać, to potrzeba (o ile P != NP) czasu wykładniczego (NP - non-polynominal).
Jeśli można sprawdzać łatwo (w czasie P), to ludzie zaczęli żywić nadzieję, że także istnieje sposób aby szybko (też w czasie P) szukać. Wiele problemów jest problemami NP i wszystkie te problemy są sobie równoważne. Równoważność oznacza, że jak uda się jeden z tych problemów rozwiązać (znaczy wyszukiwać) w czasie P, to uda się też dla wszystkich innych problemów z tej klasy (z klasy NP). Wydaje się nieprawdopodobne udowodnienie że klasa P jest równoważna NP, ponieważ dla wielu problemów nagle udałoby się zastosować szybki algorytm, którego do tej pory nikt nie odkrykł.
Kiedyś czytałem, że jakiś facio z HawletPackarda napisał pracę udowadniającą iż P != NP - na ile jego pracę potraktowano poważnie - nie wiem. Czy były inne poważne prace od tamtej pory - też nie wiem. Poczytaj pod linkami, może tam są jakieś nowe informacje i dalsze linki do ciekawych informacji.
Pozdrawiam