Вселенная задач, проверяемых компьютером, выросла. Благодаря какому секретному ингредиенту это произошло? Из-за квантовой запутанности.
Представьте, что некто пришёл к вам и заявил, что у него есть оракул, способный раскрыть сокровенные тайны вселенной. Вы могли бы заинтересоваться этим, но вам тяжело было бы в это поверить. Вы бы хотели придумать способ подтвердить, что оракул говорит правду.
Такова основная проблема информатики. Некоторые задачи слишком сложно решить за разумное время. Но их решения просто проверить. Учитывая это, специалистам по информатике хочется знать: насколько сложной может быть задача, решение которой всё ещё можно проверить?
Оказывается, что ответ на этот вопрос: практически невообразимо сложной.
Читать полностью »