Zdefiniuj klasy złożoności P (deterministyczny czas wielomianowy) i NP (niedeterministyczny czas wielomianowy). Omów hipotetyczne scenariusze: co by się stało, gdyby udowodniono, że P = NP? A jakie są konsekwencje założenia, że P ≠ NP? Wyjaśnij pojęcie problemu NP-zupełnego i podaj przykłady takich problemów (np. problem satysfakcjonowalności formuł logicznych - SAT). Omów teoretyczne znaczenie redukcji wielomianowej w klasyfikacji tych problemów.