Краткое руководство по сложным вычислительным задачам

[phenik]

Исследователи не знают, содержится ли BQP в NP, но они считают, что два этих класса сравнивать нельзя – есть задачи, входящие в NP, но не входящие в BQP, и наоборот.

18-летний Ювин Тан доказал, что классические компьютеры могут решать «задачу рекомендаций» почти так же быстро, как квантовые.
Можно сказать, что BQP задачу он свел к NP задаче?

[aleksandrpetrov14268]

Парень скрестил идею из квантового алгоритма с существующими классическими алгоритмами и получил новый алгоритм для решения контретной задачи.

[phenik]

Из вашего коммента не понятно, что вы хотели сказать. Вопрос не корректно поставлен, или вы утвердительно на него ответили) Естественно, имел ввиду только этот конкретный алгоритм, а не классы. Сомнения в том, можно отнести кв. алгоритм Керенидиса и Пракаша к классу BPQ, или нет, так как использует ML. Хотя формально по оценке времени исполнения можно.

[FluffyMan]

никто пока не смог доказать, что PH отличается от P.

Почему тогда вообще выделили отдельный класс задач?

[Drac013]

Потому что это все-таки два разных признака. И вопрос в том, следует ли из того, что если объект обладает одним из них, то он обладает и вторым, или не следует.

[sena]

Потому что существуют задачи (типа разложения на множители), для которых пока не нашли P-решения. Подозревают что это невозможно, но доказать пока не могут.

[Arranticus]

Очевидно, потому что и их равенство доказать не смогли.

[TwoBlueCats]

В описании задач в классе PSPACE вы написали, что время работы может быть, главное ограниченное число памяти

Они считают, что существуют задачи, входящие в EXP, но не входящие в PSPACE, потому что иногда для решения задачи из EXP требуется очень много времени

Можете тогда ещё раз кратко объяснить, почему мы смотрим на время при сравнении EXPTIME и PSPACE?