Теория вычислительной сложности
1

Введение

Теория вычислительной сложности.

Изначально, во времена, когда не было вычислительных машин, никто не задумывался о сложности задач. Все задачи решались наиболее комфортабельными для человека методами.

При появлении первых вычислительных машин, все находились в состоянии «эйфории» и предполагали, что все сделает машина. И действительно, для некоторых задач такой подход проходил, без каких-либо вопросов. Но чем больше ЭВМ эксплуатировалась, тем чаще стали замечать, что некоторые задачи решаются хорошо, а некоторые плохо. Сначала все сваливалось на пишущего программу, что якобы он не смог придумать хорошую программу, которая позволит решить исходную задачу. Позднее люди стали понимать, что никто ничего не может сделать, а значит что-то тут не так и дело не в людях.

В конце 60-х годов начала появляться теория вычислительной сложности, которая помогала сравнивать быстродействие алгоритмов  и описывать время их исполнения, необходимый объем памяти, в зависимости от исходных данных.

Количество элементарных операций, затрачиваемых алгоритмом, зависит не только от размера входных данных, но и от самих данных. Для того чтобы избежать трудностей, которые могут возникнуть из-за различия входных данных, возникло понятие: «временная сложность алгоритма в худшем случае».

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

Будем говорить, что f(n) =O(g(n)), если существует такая константа с, что f(n)≤c*g(n) для любого n≥0.

Полиномиальный алгоритм это алгоритм сложности O(p(n)), где p(n)-некоторая полиномиальная функция, а n-длина входных данных.

Класс NP-полных задач.

В классе NP-полных задач все задачи полиномиально сводимы друг к другу.

Началом теории NP-полных задач послужила работа С. Кука опубликованная в 1971 г. В своей работе он подчеркнул несколько важных аспектов данной теории.

  Во-первых, он подчеркнул важность понятия “сводимость за полиномиальное время”, т.е. сводимость с помощью алгоритма полиномиальной сложности. Если одна задача сводится к другой, за полиномиальное время, то любой полиномиальный алгоритм решения второй задачи может быть превращен в алгоритм решения первой задачи.

Во-вторых, он обратил внимание на класс задач распознавания свойств (класс NP), которые могут быть решены за полиномиальное время на недетерминированном вычислительном устройстве.  Большинство не поддающихся решению задач, после переформулировки их в виде задач распознавания, попадают в этот класс.

В-третьих, С. Кук доказал, что одна конкретная задача из NP, называемая задачей о SAT, обладает теми же свойствами, что и любая другая задача из класса NP и может быть сведена к ней за полиномиальное время. Таким образом, получаем, что если задача о SAT может быть решена за полиномиальное время, то и всякая другая задача из класса