Сравнительно давно в информатике и криптографии сформировалась проблема, которую пока не удалось решить ученым, работающим в этих областях. Наиболее просто она звучит так – «Легче ли проверить правильность решения проблемы, чем решить ее?». Специалисты называют ее более кратко – «NP против P». Решение этой фундаментальной задачи может дать безошибочный ответ на вопрос о том, могут ли данные быть безопасно зашифрованы.
Весьма маловероятно, что P = NP. В этом случае все системы шифрования становятся небезопасными. Если же предположить, что P неравно NP, не представляется возможным узнать, как получить действительно безопасную систему шифрования. Данная проблема сложна и имеет несколько подпроблем, лежащих в ее основании. Одна из них обозначена в науке, как проблема «EXP против BPP». Она рассматривает возможность случайно экспоненциально ускорить вычисления.
Можно ли вводом случайных чисел сделать вычисления более эффективными? Это выглядит полным безумием. Если допустить, что такое возможно, то все системы шифрования оказываются крайне ненадежными и могут быть взломаны путем «атак грубой силы», когда применяются все возможные ключи. Ученые подошли к решению этой проблемы, исследовав связь между схемами шифрования и ограниченной во времени сложностью Колмогорова.
Путем построения логических умозаключений и глубокого анализа ученые установили, что главным условием получения нерушимого шифрования может быть доказательство того, что в принципе невозможно создать алгоритм, способный безошибочно решить данную проблему. И, хотя, доказать, что такого алгоритма нет, они так и не смогли, удалось выяснить, что прийти к пониманию противоречий возможно через решение сложности Левина-Колмогорова. Это позволит не только поставить точку в проблеме «EXP против BPP», но и сделать выводы о возможности создания надежных систем шифрования.