Если n – число, которое разлагают на множители, то да, log(n)^3. Квантовая часть там заключается в том числе и в возведении в степень по модулю, там за линейное число шагов вроде бы не получается (это тоже квантовая часть, поскольку это нужно делать в суперпозиции состояний).
Теперь о связи. На самом деле под «временем» понимаются не физическое время (секунды или часы), а количество шагов алгоритма. Вопрос P?=NP заключается в том, можно ли построить (абстрактную) машину Тьюринга, которая решает любую задачу из класса NP за полиномиальное относительно длины входа число шагов. Даже если квантовое устройство позволит это сделать быстрее, к решению первоначальной задачи (построить МТ) это не относится. Я вот такую аналогию предложу: вопрос в том, сможет ли человек пробежать стометровку за восемь секунд, а вы говорите, что вот на велосипеде проехать точно сможет. Сможет-то сможет, но вопрос не в том :)
К вопросу практического решения NP-полных задач это может иметь отношение, но пока не очень ясно какое: квантовых полиномиальных алгоритмов для этих задач нет и не предвидится, возможность реализации «в железе» тоже пока под вопросом.
С квантовыми вычислениями ковыряются потихоньку, но универсальным методом это вряд ли станет. В «обычном» случае получается полиномиальное ускорение, что хорошо, но до разрыва между P и NP-complete не дотягивает.
Не за O(1), а за O(n^3).
Задача P=NP – о классической машине Тьюринга, и даже если существует методы быстрого решения NP-полных задач на квантовых компьютерах, к сути проблемы это вряд ли относится.
Есть разница между наукой и технологией. Разработка и анализ нетривиального алгоритма – вполне научное занятие, реализация его в коде – скорее, технология. Да, границы размыты, но назвать Кнута или Дейкстру «системными инженерами» как-то язык не поворачивается. Именно для такого направления нет хорошего русского слова.
А проблема P=NP – это тоже курсы под ворду, фотошопу?
Разберитесь в вопросе сначала. Школьная математика, например, тоже от науки математики очень далека, но это не значит, что «математика» – модный бренд для курсов счета и решения уравнений по готовым правилам.
Идти на факультет вычислительной математики и жаловаться на то, что там преподают математику – по меньшей мере странно. Кроме того, если она не нужна тебе – это вовсе не означает, что она не нужна никому.
«According to Don McCullin in his autobiography „Unreasonable Behaviour“, director Michelangelo Antonioni was unhappy with the colour of the grass in Maryon Park. He had it sprayed green so he could re-shoot the scene.» www.imdb.com/title/tt0060176/trivia
Если "Матрица" влияет на мировоззрение, то можно посоветовать читать больше книг, они рулез. Ну и фильмы – они же не только для драйва, это все равно, что оценивать спиртные напитки по количеству алкоголя.
В общем, конечно, каждому нравятся разные фильмы, но говорить о лучшем фильме за всю историю только на основании этого личного мнения - немножко самонадеянно, вам не кажется?
Вот этот идеологический посыл, которым вы восторгаетесь – обычное такое себе мессианство средней руки (Лоуренс Аравийский мне не кажется хуже), а весь "матричный" киберпанк обглодан фантастами давным-давно (и мне все равно, что тема "в кино не раскрыта" - это вообще странный подход, ну и, в конце концов, "Газонокосильщик" уж точно был раньше). Актерская игра средняя, характерная для многих американских фильмов. Съемка со спецэффектами неплоха, но за их вычетом - ничего особенного (и даже в таком стиле "Эквилибриум" лично меня больше впечатляет - не вижу качественной границы между ними). Но на самом деле о всех этих деталях можно спорить очень долго, а суть в том, что "Матрица" - добротное повествование с экшном, а лучшие фильмы того же Феллини, Бергмана, Линча - полусозерцательный мир в себе. Это нельзя до конца объяснить, можно только почувствовать (или не почувствовать).
Ну и помимо всего прочего, ценность Феллини доказана временем, а Матрица еще молода. Возможно, через десяток лет она будет восприниматься как "Трон" :)
Точно не помню, но в течении жизни эффект вроде бы ожидался, что для научных открытий далеко не всегда верно :) Ну это про коллайдер, с сигналом действительно нюансов гораздо больше.
А вам так кажется, что БАК - это "Золотой шар", мгновенно исполняющий желания?
Опыты Резерфорда сто лет назад тоже вряд ли казались сильно меняющими жизнь, и однако же...
Теперь о связи. На самом деле под «временем» понимаются не физическое время (секунды или часы), а количество шагов алгоритма. Вопрос P?=NP заключается в том, можно ли построить (абстрактную) машину Тьюринга, которая решает любую задачу из класса NP за полиномиальное относительно длины входа число шагов. Даже если квантовое устройство позволит это сделать быстрее, к решению первоначальной задачи (построить МТ) это не относится. Я вот такую аналогию предложу: вопрос в том, сможет ли человек пробежать стометровку за восемь секунд, а вы говорите, что вот на велосипеде проехать точно сможет. Сможет-то сможет, но вопрос не в том :)
К вопросу практического решения NP-полных задач это может иметь отношение, но пока не очень ясно какое: квантовых полиномиальных алгоритмов для этих задач нет и не предвидится, возможность реализации «в железе» тоже пока под вопросом.
Не верите википедии – возьмите классическую книгу Гэри, Джонсон «Вычислительные машины и труднорешаемые задачи».
Задача P=NP – о классической машине Тьюринга, и даже если существует методы быстрого решения NP-полных задач на квантовых компьютерах, к сути проблемы это вряд ли относится.
Разберитесь в вопросе сначала. Школьная математика, например, тоже от науки математики очень далека, но это не значит, что «математика» – модный бренд для курсов счета и решения уравнений по готовым правилам.
«According to Don McCullin in his autobiography „Unreasonable Behaviour“, director Michelangelo Antonioni was unhappy with the colour of the grass in Maryon Park. He had it sprayed green so he could re-shoot the scene.»
www.imdb.com/title/tt0060176/trivia
эта идея так и просится :)
В общем, конечно, каждому нравятся разные фильмы, но говорить о лучшем фильме за всю историю только на основании этого личного мнения - немножко самонадеянно, вам не кажется?
ЗЫ: Как я и говорил - объяснить это нельзя :)
Ну и помимо всего прочего, ценность Феллини доказана временем, а Матрица еще молода. Возможно, через десяток лет она будет восприниматься как "Трон" :)
Извините, очень похоже.
Опыты Резерфорда сто лет назад тоже вряд ли казались сильно меняющими жизнь, и однако же...