В сентябре 2021 года математик Мартин Доуд выложил в открытый доступ свое решение одной из самых известных «задач тысячелетия» — доказательство P≠NP. Но торжества по этому поводу длились недолго. Задача, судя по всему, устояла: после ряда критических замечаний к работе Доуд снял ее с публикации. Математик Владимир Потапов рассказывает о задаче, которой бросил вызов его американский коллега, и том, что, по-видимому, пошло не так. Проблема, которую принято кратко записывать формулой «P ≠ NP?», пожалуй,...

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