Палиндром — это строка, которая читается одинаково слева направо и справа налево ("А РОЗА УПАЛА НА ЛАПУ АЗОРА"). Задача поиска самой длинной палиндромной подстроки внутри гигантского текста часто встречается в биоинформатике (поиск симметричных последовательностей в молекулах ДНК) и криптоанализе. Простой перебор всех возможных центров и расширение от них дает сложность O(N^2). В 1975 году Гленн Манакер (Glenn Manacher) создал невероятно элегантный алгоритм, решающий эту задачу за строго линейное время O(N).

Регулярные выражения (Regex) — невероятно мощный инструмент для парсинга текста. Разработчики используют их для проверки email-адресов, номеров кредитных карт и телефонных кодов. Однако у них есть фундаментальный математический изъян: конечные автоматы, стоящие за регулярными выражениями, "не умеют считать". Как строго доказать, что какую-то строку невозможно распарсить с помощью Regex? Для этого в дискретной математике создана Лемма о разрастании (Pumping Lemma).

Когда речь заходит о теории сложности, большинство ограничивается обсуждением проблемы P против NP. Однако вселенная вычислительных задач гораздо шире и многообразнее. В дискретной математике и теории алгоритмов существует сложная иерархия классов, которая помогает понять пределы возможностей не только современных процессоров, но и будущих квантовых компьютеров. Что происходит, когда задача требует не просто бесконечного времени, но и бесконечной памяти?