2.2. Классы сложности

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

Учитывая необходимость кодирования данных, подаваемых на вход машине Тьюринга, эти задачи абсолютно эквивалентны задачам распознавания языков, когда на некотором алфавите Σ рассматривается подмножество слов , и для произвольного слова нужно определить, принадлежит ли оно языку L.

Суть подхода к определению наиболее сложных задач, называемых универсальными, состоит в сведении к ним любой переборной задачи. Решение универсальной задачи в этом смысле дает решение любой переборной задачи и поэтому универсальная задача оказывается не проще любой из переборных задач.

Определение 10. Говорят, что неотрицательная функция не превосходит по порядку функцию и пишут , если существует такая константа C, что для любого .

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

Например, трудоемкость означает, что время работы соответствующего алгоритма не зависит от длины входного слова ( ).

Алгоритмы с трудоемкостью называются линейными.

Алгоритм, сложность которого равна , где c – константа, называется полиномиальным.

Встречаются алгоритмы сложность которых оценивается .

Для алгоритма со сложностью (или )говорят, что он имеет экспоненциальную сложность.

Лекция 6