Вопрос о равенстве классов сложности P и NP является одной из самых фундаментальных и нерешенных проблем в компьютерной науке и математике. Проще говоря, P – это класс задач, для которых существует алгоритм, решающий их за полиномиальное время, то есть время, растущее как полином от размера входных данных. NP – это класс задач, для которых, если нам дано решение, мы можем проверить его корректность за полиномиальное время. На первый взгляд, интуитивно кажется, что задача проверки решения (NP) должна быть проще, чем задача его нахождения (P)...