MIP*=RE

MIP — это класс языков, которые распознаются эффективным алгоритмом проверки, который имеет доступ к доказывателям произвольной вычислительной мощности. Если разрешить доступ к нескольким доказывателям, у которых к тому же есть общее квантово запутанное состояние, получится класс MIP*. Оказывается, этот класс совпадает с классом всех рекурсивно перечислимых языков; в частности, он содержит проблему останова.

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

Одним из следствий доказанного равенства классов является отрицательное решение проблемы Конна (Connes embedding problem) в теории алгебр фон Неймана.

Источник: arxiv.org

Комментарии: