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

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

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