Поговорим о сложности. Немного вышедшая из моды тема "P vs NP ". О чем же идет речь? Многие задачи сводятся к перебору на конечном множестве. Скажем, поиск или сортировка. И разные алгоритмы имеют различную сложность, то есть число операций из заданного набора допустимых операций. Например, команд процессора или (в случае сортировки) сравнений. Вот есть сортировка методом пузырька: каждый элемент сравнивается с соседними и меняется с ними местами, если надо. Как бы всплывает. А есть более эффективные алгоритмы, например QuickSort...

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