Комментарии 8
Исследователи не знают, содержится ли BQP в NP, но они считают, что два этих класса сравнивать нельзя – есть задачи, входящие в NP, но не входящие в BQP, и наоборот.18-летний Ювин Тан доказал, что классические компьютеры могут решать «задачу рекомендаций» почти так же быстро, как квантовые.
Можно сказать, что BQP задачу он свел к NP задаче?
0
Парень скрестил идею из квантового алгоритма с существующими классическими алгоритмами и получил новый алгоритм для решения контретной задачи.
0
Из вашего коммента не понятно, что вы хотели сказать. Вопрос не корректно поставлен, или вы утвердительно на него ответили) Естественно, имел ввиду только этот конкретный алгоритм, а не классы. Сомнения в том, можно отнести кв. алгоритм Керенидиса и Пракаша к классу BPQ, или нет, так как использует ML. Хотя формально по оценке времени исполнения можно.
0
никто пока не смог доказать, что PH отличается от P.
Почему тогда вообще выделили отдельный класс задач?
0
Потому что это все-таки два разных признака. И вопрос в том, следует ли из того, что если объект обладает одним из них, то он обладает и вторым, или не следует.
0
Потому что существуют задачи (типа разложения на множители), для которых пока не нашли P-решения. Подозревают что это невозможно, но доказать пока не могут.
0
Очевидно, потому что и их равенство доказать не смогли.
0
В описании задач в классе PSPACE вы написали, что время работы может быть, главное ограниченное число памяти
Можете тогда ещё раз кратко объяснить, почему мы смотрим на время при сравнении EXPTIME и PSPACE?
Они считают, что существуют задачи, входящие в EXP, но не входящие в PSPACE, потому что иногда для решения задачи из EXP требуется очень много времени
Можете тогда ещё раз кратко объяснить, почему мы смотрим на время при сравнении EXPTIME и PSPACE?
0
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Краткое руководство по сложным вычислительным задачам