Cтраница 2
После того как теория, объяснявшая, какие задачи могут и какие не могут быть решены компьютером, стала хорошо разработанной, было естественно задаться вопросом о сравнительной вычислительной сложности вычислимых функций. Этим и занимается теория сложности вычислений. Рабин предложил аксиоматический подход, заложивший основы абстрактной теории сложности, развитой Блюмом [6] и другими. [16]
Единственное нетривиальное использование квантовых свойств для вычислений, которое мы уже рассмотрели, - это решение универсальной переборной задачи алгоритмом Гровера, изложенным в разделе 8.1. К сожалению, при этом достигается лишь полиномиальное ускорение. Поэтому никаких серьезных следствий для теории сложности вычислений ( типа BQP D ВРР) алгоритм Гровера не дает. В настоящее время нет доказательства того, что квантовые вычисления превосходят по скорости классические вероятностные. Но есть косвенные свидетельства в пользу такого утверждения. Первое из них - пример задачи с оракулом ( т.е. процедурой типа черного ящика), для которой существует полиномиальный квантовый алгоритм, в то время как любой классический вероятностный алгоритм экспоненциален. В дальнейшем мы решим также задачу о скрытой подгруппе в TLk, обобщающую все результаты из этого раздела. [17]
Интерес к сложности вычислений можно обнаружить во многих областях математики, в которых алгоритмы определяются, анализируются и сравниваются по их эффективности. С другой стороны, вряд ли в этих областях математики предпринимались систематические попытки развить теорию сложности вычислений, в которой изучались бы количественные проблемы, связанные с вычислениями. Проблемы сложности первоначально не были достаточно хорошо определены, и даже в период быстрого развития конструктивной математики в первой половине нашего века на них не смотрели как на самостоятельную область. В то время были определены некоторые классификации подклассов рекурсивных функций, но главный интерес был скорее в единообразном построении все более и более широких подклассов рекурсивных функций, чем в изучении внутренней вычислительной сложности функций. [18]
В силу таких эквивалентностей если за полиномиальное время разрешима одна из этих задач, то все остальные тоже разрешимы. Вопрос о том, имеет ли выполнимость полиномиальную сложность, называется проблемой P NP и справедливо считается самой знаменитой задачей теории сложности вычислений. [19]
Общее число таких операций, выполняемых в процессе построения, называется его простотой, хотя Лемуан полагал, что, возможно, более уместен термин мера сложности. Это определение близко связано с нашей современной идеей временной сложности алгоритма, хотя в работе Лемуана нет функциональной связи между размером исходной информации ( числом заданных точек и линий) для геометрического построения и его простотой. Безусловно, интерес Лемуана был направлен на улучшение исходных евклидовых построений, а не на развитие теории сложности вычислений. К сожалению, Лемуан не почувствовал важности доказательства, а возможно, просто не смог доказать, что определенное число операций было необходимо для данного построения, и, таким образом, идея о нижней оценке алгоритма ускользнула от него. [20]