Представьте два одинаковых сундука с сокровищами: внешне их не отличить, но в одном — награда, а в другом — ловушка. Никаких хитростей, чтобы их распознать, нет: придется открывать каждый отсек, чтобы убедиться.

Ученые из Пекинского университета аэронавтики и Пекинского технологического университета доказали, что с некоторыми компьютерными «загадками» — то же самое. Короткого пути нет: нужно перебрать все варианты.

Результаты опубликованы в издании Frontiers of Computer Science.

Почему это важно для обычных технологий

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

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

Как это доказали

Исследователи создали особые задачи-головоломки, в которых нельзя действовать наугад. Они подготовили пары задач, внешне идентичных, но с противоположными результатами. Как с сундуками: никакой беглый осмотр не покажет, где решение ( «приз»), а где его нет („ловушка“).

Единственный способ — проверить все варианты. Ученые использовали хитрый прием: скрыто «меняли местами» детали между двумя версиями задачи, делая их неразличимыми без полного перебора.

Мы хотели точно определить, где уловки перестают работать, — объясняет профессор Ке Сюй.

Они показали, что любой алгоритм, каким бы умным он ни был, не обнаружит подмену без полного перебора. Хотя математика здесь отсылает к классическим идеям «неполноты», суть проста: если создать „близнецов“ с секретной заменой, придется проверять все.

Что это значит

Это не значит, что все сложные задачи требуют полного перебора. В реальном мире чаще работают эвристики, упрощения или фокус на типичных случаях. Но такие «беспроигрышные» примеры — четкий сигнал: в некоторых редких областях без перебора не обойтись. Осознание этих границ помогает ученым не тратить силы впустую и сосредоточиться на том, где прогресс возможен.

Эвристика — это «умный» способ решать задачи быстрее, но не всегда точно. Например, вместо проверки всех маршрутов навигатор выбирает самый вероятный — это эвристика.

Кроме практической пользы, этот подход — отличный пример для теории. Он наглядно показывает, когда «грубая сила» — единственный вариант, и может вдохновить на подобные исследования в других областях.

Главная ценность работы — в четком определении границ. Зная, что для определенного класса задач нет алгоритмических сокращений, разработчики могут:

• Оптимизировать ресурсы: не тратить время на поиск несуществующих решений.
• Улучшать криптографию: такие задачи идеальны для создания «невзламываемых» ключей.
• Развивать ИИ: понимание пределов помогает обучать модели эффективнее.

Пример: если в шифровании использовать подобные «близнецовые» задачи, взлом потребует полного перебора, что делает защиту надежнее.

Исследование фокусируется на искусственно созданных задачах, которые редко встречаются в практике. Хотя это ценно для теории, применимость в реальных системах ограничена: большинство задач все же имеют «слабые места» для оптимизации.

Ранее ученые разработали новое шифроваие, усиливающее безопасность систем.