Среди тысяч алгоритмических задач существует одна, которая носит титул "самой важной задачи теоретической информатики". Это задача о выполнимости булевых формул, сокращенно SAT (от англ. Satisfiability). Она стала первой в истории задачей, для которой была математически доказана принадлежность к классу NP-полных задач, и именно к ней сводятся все доказательства сложности в дискретной математике.

В любом классическом учебнике по алгоритмам написано, что лучшая возможная сложность для сортировки массива — это O(N log N). Эту асимптотику выдают быстрая сортировка (QuickSort) и сортировка слиянием (MergeSort). В дискретной математике существует строгое доказательство того, что сортировки, основанные на сравнении элементов, физически не могут работать быстрее. Но что, если мы откажемся от операций сравнения? Здесь на сцену выходят алгоритмы сортировки за линейное время O(N).

На протяжении десятилетий алгоритм RSA обеспечивал безопасность интернета. Его надежность базируется на сложности факторизации больших целых чисел. Но с ростом вычислительных мощностей математикам приходилось постоянно увеличивать размер RSA-ключей. Сегодня безопасный ключ RSA должен иметь длину 2048 или даже 3072 бита. Такие ключи требуют много памяти и сильно замедляют процессоры смартфонов и IoT-устройств. Спасение пришло из абстрактной алгебраической геометрии — криптография на эллиптических кривых (ECC).

Задача поиска слова (паттерна) внутри большого текста (строки) — одна из самых частых в компьютерных науках. Наивный алгоритм, который мы бы написали интуитивно, прикладывает паттерн к началу текста, сравнивает символы, и при несовпадении сдвигает паттерн ровно на одну позицию вправо, начиная проверку с нуля. В худшем случае (например, поиск паттерна "ААААВ" в строке "АААААААААВ") этот метод работает за время O(N*M), что неприемлемо. Алгоритм КМП решает эту проблему за строго линейное время O(N+M).