Задача 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]
Попозже..
Да, когда-угодно, хоть через год. Манипуляция течением времени внутри компьютера (даже на микроуровне) – это явно что-то из области далёкой фантастики. Просто интересен развёрнутый ответ.
:)
Надо же, именно эта работа была недавно помянута[link2]:
Наверно, по CTC лучше продолжать тут, а то там были топики в целом о другом.
Забавная статья: Путешествия во времени без сожалений[link3]. Но даже на уровне мурзилки мало что понятно, хотя там пытались объяснить на пальцах. Всё, что понял — grandfather paradox допускать ни в коем случае нельзя, а то принципу причинности кирдык. Оригинал статьи[link4] не читал.