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