Задача 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
комментариев: 1515 документов: 44 редакций: 5786
комментариев: 9796 документов: 488 редакций: 5664
Надо же, именно эта работа была недавно помянута:
Наверно, по CTC лучше продолжать тут, а то там были топики в целом о другом.
Забавная статья: Путешествия во времени без сожалений. Но даже на уровне мурзилки мало что понятно, хотя там пытались объяснить на пальцах. Всё, что понял — grandfather paradox допускать ни в коем случае нельзя, а то принципу причинности кирдык. Оригинал статьи не читал.