Cтраница 1
Теория сложности обнаруживает, что эта комбинация локальной случайности и глобального порядка порождает процессы, которые более устойчивы по отношению к окружающим условиям. Это означает, что они могут адаптироваться к окружающим условиям, реагируя, на первый взгляд, непредсказуемым образом. Их поведение непредугадываемо, и поэтому они выигрывают в соревновании с другими видами или системами. Статические системы, реагирующие линейно, обречены на вымирание. Их приспособительные возможности исчерпываются в борьбе с более адаптированными конкурентами. [1]
Теория сложности в основном связана с ограничениями, связанными с вычислением функций: какие функции могут быть вычислены, как быстро и с использованием какого объема памяти. С квантовыми компьютерами, как и с классическими вероятностными компьютерами следует вопрос и с какой вероятностью. Теория сложности для Q позволяет провести дальнейшее исследование. [2]
Теория сложности занимается не столько изучением трудностей, связанных с решением отдельных задач, сколько с бесконечными семействами задач, в каждом из которых любая задача может быть решена с помощью одного и того же алгоритма. Чуть позднее я объясню более подробно, как фактически этот номер п характеризует размер задачи. Для определенности договоримся, что N - это наибольшее число шагов среди всех задач данного размера п, которое может понадобиться алгоритму для решения. [3]
Теория сложности является важной для наших рассуждений в этой книге не только потому, что она касается вопроса возможности алгоритмизации, но и потому, что она позволяет для заведомо алгоритмизуе-мых объектов решать вопрос о том, могут ли использоваться соответствующие алгоритмы на практике. В последующих главах я буду больше говорить о вычислимости, чем о теории сложности, поскольку я склонен думать ( хотя, конечно, и не имея для этого достаточных оснований), что, в отличие от фундаментального вопроса вычислимости, положения теории сложности не на-столькр значимы для феномена мышления. Более того, мне представляется, что теория сложности сегодня лишь слегка затрагивает вопросы практичности алгоритмов. [4]
Теория сложности, предлагаемая здесь, машинно-независима. Это означает, что теорема, которая характеризует сложности частично рекурсивных функций на одном классе машин, одинаково хорошо характеризует их сложности на почти любом другом классе. Хотя это и не является неожиданным, все же это утверждение представляется странным, так как сложность конкретных функций неизбежно зависит от класса машин, используемых для вычислений. [5]
Теория сложности изучает сложность алгоритмов. Существует несколько способов измерения сложности алгоритма. Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны идругие показатели - требования к объему памяти, свободному месту на диске. Использование быстрого алгоритма не приведет к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у вашего компьютера. [6]
В теории сложности выделяют массовые и индивидуальные задачи. Первые из них сформулированы в общем виде, вторые представлены с конкретными числовыми значениями исходных данных. Исследования сложности проводятся в отношении массовых задач, и получаемые выводы, как правило, относятся к наихудшему случаю - к наиболее неблагоприятному возможному сочетанию исходных данных. [7]
Область теории сложности ни в коей мере не ограничивается алгебраическими или арифметическими вычислениями. Рассмотрим контекстно-свободные грамматики, из которых в качестве примера возьмем следующую. Среди этих символов t нетерминальный, а все остальные - терминальные. [8]
Сборка теории сложности из кусков. [9]
Не распространена теория сложности и на задачи принятия оперативных решений. [10]
Из результатов теории сложности следуют важные практические рекомендации: 1) приступая к решению некоторой комбинаторной задачи, необходимо сначала проверить, не принадлежит ли она к классу NP-полных задач, и если это так, то не следует тратить усилия на разработку алгоритмов и программ точного решения; 2) отсутствие эффективных алгоритмов точного решения массовой задачи выбора отнюдь не означает невозможности эффективного решения индивидуальных задач из класса NP-полных или невозможности получения приближенного решения по эвристическим алгоритмам за полиномиальное время. [11]
Обсуждается предмет теории аналитической сложности и этой книги. [12]
Основной вопрос теории сложности дискретных алгоритмов состоит в доказательстве или опровержении гипотезы о том, что Р NP. Если гипотеза справедлива, то для решения наиболее трудных задач класса NP полиномиальных алгоритмов не существует. [13]
Критерием эффективности в теории сложности служит временная сложность алгоритма как функция входной длины задачи. [14]
Этот проект для теории сложности оказался своего рода неожиданным подарком судьбы, но я очень отчетливо чувствую: что в целом информатика давно не финансировалась так плохо. Национальный научный фонд поддерживает несколько очень достойных новых инициатив, но это делается без соответствующего расширения финансовой основы, так что эти инициативы субсидируются за счет уже существующих программ. Хотя я должен сказать, что программа ИМН является исключением, в целом люди, занимающиеся теоретической информатикой, потеснены уменьшением финансирования вследствие смещения приоритетов ННФ - в основном в сторону инженерных исследований. [15]