Задача P=NP и даже P=PSPACE может быть решена на неквантовых компьютерах

Scott Aaronson из MIT и John Watrous из университета Ватерлоо придумали теоретическую модель, с помощью которой можно решать задачи класса NP и PSPACE за полиноминальные затраты памяти на классических компьютерах и полиномиальные затраты времени на квантовых.

Он это даже как-то доказали.

Но есть одно небольшое, но...

Такой компьютер должен иметь доступ к CTC (Closed Timeline Curves) – замкнутым временно-подобным кривым, описанным в решении Геделя для уравнений общей теории относительности. При этом не используются такие сложные топологии как червоточины или струны.

Может spinore более подробно просвятит на эту тему, это как-то связано с коллайдером?

Closed Timelike Curves Make Quantum and Classical Computing Equivalent

Комментарии

—	spinore (10/10/2008 14:08) профиль/связь <#> комментариев: 1515 документов: 44 редакций: 5786

Попозже..

—	unknown (10/10/2008 14:45) профиль/связь <#> комментариев: 9796 документов: 488 редакций: 5664

Да, когда-угодно, хоть через год. Манипуляция течением времени внутри компьютера (даже на микроуровне) – это явно что-то из области далёкой фантастики. Просто интересен развёрнутый ответ.

—	*Гость* (10/10/2008 20:07) <#>

closed timelike curves (CTCs) are not known to exist

—	*Гость* (19/02/2014 09:57) <#>

> Closed Timelike Curves Make Quantum and Classical Computing Equivalent

Надо же, именно эта работа была недавно помянута:

Квантовые компьютеры — это вчерашний день. Используя CTC-computation можно задействовать машину времени для лёгкого и непринуждённого решения задач, приравняв наконец-то P=NP. Описание есть в конце забавной мурзилки The Limits of Quantum Computers или в ряде работ, наподобие Closed Timelike Curves Make Quantum and Classical Computing Equivalent.

Наверно, по CTC лучше продолжать тут, а то там были топики в целом о другом.

Забавная статья: Путешествия во времени без сожалений. Но даже на уровне мурзилки мало что понятно, хотя там пытались объяснить на пальцах. Всё, что понял — grandfather paradox допускать ни в коем случае нельзя, а то принципу причинности кирдык. Оригинал статьи не читал.

Ваша оценка документа [показать результаты]