Сложность алгоритмов

Введение
С понятием алгоритма были знакомы еще ученые древних цивилизаций. Алгоритм Евклида нахождения наибольшего общего делителя двух целых чисел был описан в книге VII «Начал» Евклида, датирующейся 330-320 гг. до н.э. Прообраз метода исключения Гаусса был описан в китайском источнике «Девять книг по арифметике» (202 г. до н.э. — 9 г.н.э.). Эратосфен (приблиз. 276–194 гг. до н.э.) предложил алгоритм проверки простоты числа, получивший впоследствии название решета Эратосфена.
Тем не менее, различные формализации понятия алгоритма были предложены только в середине 30-х годов прошлого столетия, когда и стала складываться современная теория алгоритмов. Ее возникновение связано с точным математическим определением такого, казалось бы, интуитивно ясного понятия как алгоритм. Потребность в этом определении была вызвана внутренними тенденциями развития математики, поскольку некоторые открытые проблемы заключались в выяснении существования (или несуществования) алгоритма для решения конкретных задач. Например, знаменитая 10-я проблема Гильберта заключалась в вопросе о существовании процедуры нахождения целочисленных корней произвольного многочлена от нескольких переменных с целыми коэффициентами.
Именно потенциальная возможность несуществования алгоритмов решения некоторых проблем потребовала формального определения алгоритма. Почти одновременно в 30-х годах XX века независимо (и в разных формах) рядом крупных математиков того времени — А. Тьюрингом, А. Черчем, Э. Постом, К. Геделем, С. Клини и др. — было формализовано понятие вычислимости.
Э. Пост и А. Тьюринг определили алгоритм как вычисление на абстрактных машинах. При этом вычислимость функции понималась как вычислимость на машинах Тьюринга. К. Гедель, А. Черч и С. Клини определили понятие вычислимости по-другому, на языке введенных ими арифметических функций, которые теперь называются частично рекурсивными функциями. Позднее А.А. Марков ввел понятие нормального алгоритма. Однако выяснилось, что все эти...

1. Сложность алгоритмов
Под алгоритмом обычно понимают четко определенную последовательность действий, приводящую через конечное число шагов к результату — решению задачи, для которой разработан алгоритм.
Основные свойства, присущие любому алгоритму:
1. массовость — алгоритм предназначен для решения задачи с некоторым множеством допустимых входных данных;
2. конечность — алгоритм должен завершаться за конечное число шагов (но это количество шагов может быть разным для разных входных данных).
Задачи могут быть сформулированы по-разному (дифференциальные уравнения, задачи на графах, задачи оптимизации и т.п.). Для того чтобы можно было строить единую теорию алгоритмов, необходимо свести разные формулировки задач к какому-то «единому знаменателю». Например, можно считать, что задача сводится к вычислению некоторой функции F:X→Y. Ясно, что в таком виде можно сформулировать любую задачу. Но для некоторых задач функция F может быть выражена неявно. Например, для задачи поиска минимума функции ϕ на отрезке [0,1] имеем: X = множество
функций, Y = [0,1], F(ϕ) = x*: ϕ(x*) = min{ϕ(x): x ∈ [0,1]}.
Не для любой задачи можно построить алгоритм. Существуют алгоритмически неразрешимые задачи.
Проблема алгоритмической разрешимости задачи тесно связана с требованием массовости алгоритма. Алгоритмическая неразрешимость задачи означает, что для любого алгоритма A, решающего данную задачу, существует набор входных данных x, на котором алгоритм работает неверно (либо возвращает неправильный результат, либо не останавливается).
Но даже если существует алгоритм, решающий задачу, это еще не значит, что мы сможем этим алгоритмом воспользоваться на практике для решения реальных задач. Потому что алгоритм может требовать для своей работы слишком много ресурсов. Например, если решение задачи на самых современных компьютерах займет 10 лет — очевидно, такой алгоритм для нас бесполезен. Иными словами, недостаточно существования какого-нибудь алгоритма —...

Заключение
Теория сложности также классифицирует и сложность самих проблем, а не только сложность конкретных алгоритмов решения проблемы. Задачи можно разбить на классы в соответствии со сложностью их решения. Вот важнейшие из них и предполагаемые соотношения между ними:
P