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

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

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

Обзор

Вычислительную сложность алгоритма обычно выражают через символ «О прописная», что указывает порядок величины вычислительной сложности. Это просто член разложения функции сложности, которая растет быстрее при росте n, а все члены низшего порядка игнорируются. Например, если временная сложность порядка n^2, то она выражается как O(n²) ^.

Временная сложность, измеренная подобным образом, не зависит от реализации.

Не нужно знать ни точного времени выполнения отдельных инструкций, ни числа битов, которые представляют различные переменные, ни даже скорости процессора. Один компьютер может быть на 50 % быстрее другого, а у третьего ширина шины данных может быть вдвое больше, однако сложность алгоритма, оцененная по порядку величины, не изменится. При оценке довольно сложных алгоритмов всем остальным можно пренебречь (с точностью до постоянного множителя).

Оценка вычислительной сложности наглядно демонстрирует, как объём входных данных влияет на требования к времени и объёму памяти.

Например, если T=O(n), удвоение входных данных удвоит и время выполнения алгоритма. Если T=O(2ⁿ), то добавления лишь одного бита к входным данным удвоит время выполнения алгоритма.

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

Ресурсы, которые оцениваются, как уже было отмечено ранее, могут быть такими: время, пространство памяти, случайные биты, количество процессоров и т. д., но обычно главным фактором является время и реже пространство.

Теория рассматривает минимальное время и объём памяти для решения сложного варианта задачи теоретически на компьютере, известном как машина Тьюринга. Машина Тьюринга является конечным автоматом с бесконечной лентой памяти для чтения и записи. Это означает, что машина Тьюринга — реалистичная вычислительная модель.

Задачами, которые можно решить с помощью алгоритмов с полиномиальным временем, называют задачи, которые решаются — при условии нормальных входных данных — за приемлемое время (точное определение «приемлемости» зависит от конкретных условий) .

Задачи, которые можно решить только с помощью суперполиномиальных алгоритмов с полиномиальным временем, является вычислительно сложными даже при относительно малых значениях n.

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

Асимптотическая сложность

Обозначение	Интуитивное объяснение	Определение
${\displaystyle f(n)\in O(g(n))}$	${\displaystyle f}$ ограничена сверху функцией ${\displaystyle g}$ (с точностью до постоянного множителя) асимптотически	${\displaystyle \exists (C>0),n_{0}:\forall (n>n_{0})\;|f(n)|\leq C|g(n)|}$ или ${\displaystyle \exists (C>0),n_{0}:\forall (n>n_{0})\;f(n)\leq Cg(n)}$
${\displaystyle f(n)\in \Omega (g(n))}$	${\displaystyle f}$ ограничена снизу функцией ${\displaystyle g}$ (с точностью до постоянного множителя) асимптотически	${\displaystyle \exists (C>0),n_{0}:\forall (n>n_{0})\;|f(n)|\geq C|g(n)|}$
${\displaystyle f(n)\in \Theta (g(n))}$	${\displaystyle f}$ ограничена снизу и сверху функцией ${\displaystyle g}$ асимптотически	${\displaystyle \exists (C,C'>0),n_{0}:\forall (n>n_{0})\;C|g(n)|\leq |f(n)|\leq C'|g(n)|}$
${\displaystyle f(n)\in o(g(n))}$	${\displaystyle g}$ доминирует над ${\displaystyle f}$ асимптотически	${\displaystyle \forall (C>0)\exists n_{0}:\forall (n>n_{0})\;|f(n)|<C|g(n)|}$
${\displaystyle f(n)\in \omega (g(n))}$	${\displaystyle f}$ доминирует над ${\displaystyle g}$ асимптотически	${\displaystyle \forall (C>0)\exists n_{0}:\forall (n>n_{0})\;|f(n)|>C|g(n)|}$
${\displaystyle f(n)\sim g(n)}$	${\displaystyle f}$ эквивалентна ${\displaystyle g}$ асимптотически	${\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=1}$

Распространённые сложности алгоритмов

Обозначение	Пояснение	Примеры
${\displaystyle O(1)}$	Устойчивое время работы, независимо от размера задачи.	Ожидаемое время поиска в хэше.
${\displaystyle O(\log \log n)}$	Очень медленный рост необходимого времени.	Ожидаемое время работы интерполирующего поиска ${\displaystyle n}$ элементов.
${\displaystyle O(\log n)}$	Логарифмический рост — удвоение размера задачи увеличивает время работы на постоянную величину.	Вычисления; двоичный поиск в массиве из ${\displaystyle n}$ элементов.
${\displaystyle O(n)}$	Линейный рост — удвоение размера задачи удвоит и необходимое время.	Сложение/вычитание чисел из ${\displaystyle n}$ цифр; линейный поиск в массиве из ${\displaystyle n}$ элементов.
${\displaystyle O(n\cdot \log n)}$	Линеаризованный рост — удвоение размера задачи увеличит необходимое время чуть более чем вдвое.	Сортировка слиянием или множеством ${\displaystyle n}$ элементов; нижняя граница сортировки со сравнением ${\displaystyle n}$ элементов.
${\displaystyle O(n^{2})}$	Квадратичный рост — удвоение размера задачи в 4 раза увеличивает необходимое время.	Элементарные алгоритмы сортировки.
${\displaystyle O(n^{3})}$	Кубический рост — удвоение размера задачи увеличивает необходимое время в восемь раз.	Обычное умножение матриц.
${\displaystyle O(c^{n})}$	Экспоненциальный рост — увеличение размера задачи на ${\displaystyle 1}$ приводит к ${\displaystyle c}$-кратному увеличению необходимого времени; удвоение размера задачи увеличивает необходимое время в квадрат	Некоторые задачи коммивояжера, алгоритмы поиска полным перебором.

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

Класс сложности — множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Задачи можно разбить на классы согласно сложности их решения. Все классы сложности находятся в иерархическом отношении: одни содержат в себе другие. Однако о большинстве включений неизвестно, являются ли они строгими. Класс P, что является самым низким, содержит все задачи, которые можно решить за полиномиальное время. В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной машине Тьюринга (это вариант обычной машины Тьюринга, которая может делать предположения). Такая машина делает предположение относительно решения задачи или «удачно угадывает», перебирая все предположения параллельно — и проверяет свое предположение за полиномиальное время.

Класс P

Класс P (от англ. Polynomial) — множество задач, для которых существуют «быстрые» алгоритмы решения (время работы которых полиномиально зависит от размера входных данных). Класс P включен в более широкие классы сложности алгоритмов. Для любого языка программирования можно определить класс P подобным образом (заменив в определении машину Тьюринга на реализацию языка программирования). Если компилятор языка, на котором реализован алгоритм, замедляет выполнение алгоритма полиномиальной (то есть время выполнения алгоритма на машине Тьюринга меньше некоторого многочлена от времени выполнения его на языке программирования), то определение классов P для этого языка и для машины Тьюринга совпадают. Код на ассемблере допускает преобразование в машину Тьюринга с небольшим полиномиальным замедлением, а поскольку все существующие языки допускают компиляцию в ассемблер (опять же, с полиномиальным замедлением), то определения класса P для машин Тьюринга и для любого существующего языка программирования совпадают.

Класс NP

Класс NP (от англ. Non-deterministic polynomial) — множество задач, решение которых возможно при наличии некоторых дополнительных сведений (так называемого сертификата решения), то есть возможность «быстро» (за время, не превосходящее полином от размера данных) проверить решение на машине Тьюринга. Эквивалентно класс NP можно определить как совокупность задач, которые можно «быстро» решить на недетерминированной машине Тьюринга.

Класс NP определяется для множества языков, то есть множеств слов над конечным алфавитом Σ. Язык L принадлежит классу NP, если существуют двухместный предикат ${\displaystyle R(x,y)}$ из класса P (то есть исчисляемый за полиномиальное время) и константа ${\displaystyle C>0}$ такие, что для любого слова ${\displaystyle x}$ условие ${\displaystyle x\in L}$ равносильно условию ${\displaystyle \exists y,|y|<|y|}$^{${\displaystyle c}$} ${\displaystyle R(x,y)}$ .

Отношение классов сложности NP и P

В теории алгоритмов вопрос о равенстве классов сложности P и NP является одной из центральных открытых проблем уже более трех десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать много сложных задач существенно быстрее, чем сейчас. Из определения классов P и NP сразу вытекает следствие: ${\displaystyle P\subseteq NP}$ . Однако до сих пор ничего не известно о строгости этого включения, то есть существует ли задача, лежащая в NP, но не лежащая в P. Если такой задачи не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что обещает огромную выгоду с вычислительной точки зрения. Сейчас самые сложные задачи из класса NP (так называемые NP -полное задачи) можно решить за экспоненциальное время, что почти всегда неприемлемо. В настоящее время большинство математиков считают, что эти классы не равны. Согласно опросу, проведенному в 2002 году среди 100 ученых,^[1] 61 человек считает, что ответ — «не равны»; 9 — «равны»; 22 не смогли ответить; 8 считают, что гипотеза не выводится из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута. Из вышесказанного видно, что проблема исследования отношения классов P и NP является актуальной в научной среде и требует более глубокого анализа.

Неподатливость

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

История

Примером раннего анализа сложности алгоритмов является проведенный анализ алгоритма Евклида, который сделал Габриель Ламе в 1844 году.

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

Примечания

1. Gasarch W.I. «The P=?NP poll.» / William I. Gasarch SIGACT News. Volume 33. — 2002 — С. — Режим доступу: http://www.cs.umd.edu/~gasarch/papers/poll.pdf Архивная копия от 27 октября 2019 на Wayback Machine — ст. 34-47

Литература

• Christos H. Papadimitriou: Computational Complexity. Addison-Wesley, Reading / Mass. 1995, ISBN 0-201-53082-1.
• Lance Fortnow, Steve Homer: A Short History of Computational Complexity. Online-Manuskript (PDF, 225 kB)
• Jan van Leeuwen (Hrsg.): Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity. The MIT Press / Elsevier, Amsterdam 1994, ISBN 0-262-72020-5.
• Juris Hartmanis, Richard Edwin Stearns : On the computational complexity of algorithms. In: Trans. American Mathematical Society. 117/1965, S. 285—306, ISSN 0002-9947. (англ.)
• Ding-Zhu Du, Ker-I Ko: Theory of Computational Complexity. John Wiley & Sons, New York 2000, ISBN 0-471-34506-7.
• Michael R. Garey, David S. Johnson: Computers and Intractability: A guide to the theory of NP-completeness. Freeman, New York 2003, ISBN 0-7167-1045-5.
• Michael Sipser: Introduction to the Theory of Computation. 2. Auflage. Thomson, Boston 2006, ISBN 0-534-95097-3 . (International Edition)
• Кузюрин М. М., Фомин С. А. Эффективные алгоритмы и сложность вычислений. 2008
• Немировский А. С., Юдин Д. Б. Сложность и эффективность методов оптимизации. М. : Наука, 1979
• Абрамов С. А. Лекции о сложности алгоритмов. — М.: МЦНМО, 2020. — Изд. 3-е, испр. и доп. — 256 с. — ISBN 978-5-443-91464-0