id: Гость   вход   регистрация
текущее время 16:18 23/02/2020
Автор темы: unknown, тема открыта 08/10/2008 11:38 Печать
Категории: криптография, разное, офф-топик, квантовая криптография
https://www.pgpru.com/Форум/Офф-топик/ЗадачаPNPИДажеPPSPACEМожетБытьРешенаНаНеквантовыхКомпьютерах
создать
просмотр
ссылки

Задача 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)   <#>

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

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

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



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