1
Czy Stephen Cook dostrzegł znaczenie wykazania, że SAT jest NP-twardy przed faktycznym udowodnieniem?
Jeśli dobrze rozumiem, aby udowodnić, że problem jest trudny NP, musisz wybrać wszystkie możliwe problemy które są w NP, a następnie udowodnić, że redukują się do za pomocą funkcji obliczania czasu wielomianowego, która odwzorowuje wystąpienia każdego z nich do przypadków .ZAAAbjaBiB_{i}ZAAAbjaBiB_{i}ZAAA Po znalezieniu pierwszego trudnego problemu NP, stosując redukcje, możesz …