Задача 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[link1]

Комментарии
— spinore (10/10/2008 14:08)   
Попозже..
— unknown (10/10/2008 14:45)   
Да, когда-угодно, хоть через год. Манипуляция течением времени внутри компьютера (даже на микроуровне) – это явно что-то из области далёкой фантастики. Просто интересен развёрнутый ответ.
Гость (10/10/2008 20:07)   
closed timelike curves (CTCs) are not known to exist
:)
Гость (19/02/2014 09:57)   

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

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

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



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

Ссылки
[link1] http://eccc.hpi-web.de/eccc-reports/2008/TR08-092/index.html

[link2] https://www.pgpru.com/comment57374

[link3] http://physics.aps.org/story/v27/st5

[link4] http://arxiv.org/abs/1005.2219