В теоретической информатике и математике теория сложности вычислений фокусируется на классификации вычислительных задач в соответствии с использованием их ресурсов и исследует взаимосвязи между этими классификациями. Вычислительная задача — это задача, решаемая компьютером. Вычислительная задача решается путем механического применения математических шагов, таких как алгоритм .
Проблема считается изначально сложной, если ее решение требует значительных ресурсов, независимо от используемого алгоритма. Теория формализует эту интуицию, вводя математические модели вычислений для изучения этих проблем и количественно оценивая их вычислительную сложность , т. е. количество ресурсов, необходимых для их решения, таких как время и память. Также используются другие меры сложности, такие как объем коммуникации (используется в сложности коммуникации ), количество вентилей в схеме (используется в сложности схемы ) и количество процессоров (используется в параллельных вычислениях ). Одна из ролей теории вычислительной сложности заключается в определении практических ограничений того, что компьютеры могут и не могут делать. Задача P против NP , одна из семи задач Премии тысячелетия , [1] является частью области вычислительной сложности.
Тесно связанными областями в теоретической информатике являются анализ алгоритмов и теория вычислимости . Ключевое различие между анализом алгоритмов и теорией вычислительной сложности заключается в том, что первый посвящен анализу количества ресурсов, необходимых конкретному алгоритму для решения проблемы, тогда как последний задает более общий вопрос обо всех возможных алгоритмах, которые могут быть использованы для решения той же проблемы. Точнее, теория вычислительной сложности пытается классифицировать проблемы, которые могут или не могут быть решены с помощью соответствующим образом ограниченных ресурсов. В свою очередь, наложение ограничений на доступные ресурсы отличает вычислительную сложность от теории вычислимости: последняя теория спрашивает, какие виды проблем в принципе могут быть решены алгоритмически.
Вычислительную задачу можно рассматривать как бесконечную коллекцию экземпляров вместе с набором (возможно, пустым) решений для каждого экземпляра. Входная строка для вычислительной задачи называется экземпляром задачи и не должна путаться с самой задачей. В теории вычислительной сложности задача относится к абстрактному вопросу, который необходимо решить. Напротив, экземпляр этой задачи — это довольно конкретное высказывание, которое может служить входными данными для задачи принятия решения. Например, рассмотрим задачу проверки простоты . Экземпляр — это число (например, 15), а решение — «да», если число простое, и «нет» в противном случае (в этом случае 15 не является простым, и ответ — «нет»). Другими словами, экземпляр — это конкретный вход для задачи, а решение — это выход, соответствующий заданным входным данным.
Чтобы еще больше подчеркнуть разницу между задачей и примером, рассмотрим следующий пример решения задачи коммивояжера : существует ли маршрут длиной не более 2000 километров, проходящий через все 15 крупнейших городов Германии? Количественный ответ на этот конкретный пример задачи малопригоден для решения других примеров задачи, таких как запрос на круговой маршрут через все места в Милане , общая длина которых не превышает 10 км. По этой причине теория сложности рассматривает вычислительные проблемы, а не конкретные примеры задач.
При рассмотрении вычислительных задач экземпляром проблемы является строка над алфавитом . Обычно в качестве алфавита берется двоичный алфавит (т. е. множество {0,1}), и, таким образом, строки являются битовыми строками . Как и в реальном компьютере , математические объекты, отличные от битовых строк, должны быть соответствующим образом закодированы. Например, целые числа могут быть представлены в двоичной записи , а графы могут быть закодированы напрямую через их матрицы смежности или путем кодирования их списков смежности в двоичной форме.
Хотя некоторые доказательства теорем теории сложности регулярно предполагают некоторый конкретный выбор входного кодирования, мы стараемся поддерживать обсуждение достаточно абстрактным, чтобы оно не зависело от выбора кодирования. Этого можно достичь, гарантируя, что различные представления могут быть эффективно преобразованы друг в друга.
Задачи принятия решений являются одним из центральных объектов изучения в теории сложности вычислений. Задача принятия решений — это тип вычислительной задачи, где ответом является либо «да» , либо « нет» (альтернативно 1 или 0). Задачу принятия решений можно рассматривать как формальный язык , где членами языка являются экземпляры, вывод которых — «да», а не-членами — те экземпляры, вывод которых — «нет». Цель состоит в том, чтобы с помощью алгоритма решить , является ли заданная входная строка членом рассматриваемого формального языка. Если алгоритм, решающий эту задачу, возвращает ответ «да» , говорят, что алгоритм принимает входную строку, в противном случае говорят, что он отклоняет входные данные.
Примером проблемы принятия решения может служить следующий пример. Входные данные — произвольный граф . Задача состоит в определении того, является ли данный граф связным или нет. Формальный язык, связанный с этой проблемой принятия решения, — это множество всех связных графов — чтобы получить точное определение этого языка, нужно решить, как графы кодируются в виде двоичных строк.
Функциональная задача — это вычислительная задача, в которой для каждого ввода ожидается один выход ( полной функции ), но выход более сложен, чем у задачи принятия решения , то есть выход — это не просто «да» или «нет». Известные примеры включают задачу коммивояжера и задачу целочисленной факторизации .
Возникает соблазн думать, что понятие функциональных задач гораздо богаче понятия задач на принятие решений. Однако это не совсем так, поскольку функциональные задачи можно переформулировать как задачи на принятие решений. Например, умножение двух целых чисел можно выразить как набор троек, таких, что отношение выполняется. Решение вопроса о том, является ли данная тройка членом этого набора, соответствует решению задачи на умножение двух чисел.
Чтобы измерить сложность решения вычислительной задачи, можно узнать, сколько времени требуется лучшему алгоритму для ее решения. Однако время выполнения может, в общем случае, зависеть от экземпляра. В частности, более крупные экземпляры потребуют больше времени для решения. Таким образом, время, необходимое для решения задачи (или требуемое пространство, или любая мера сложности), рассчитывается как функция размера экземпляра. Размер входных данных обычно измеряется в битах. Теория сложности изучает, как алгоритмы масштабируются по мере увеличения размера входных данных. Например, в задаче определения связности графа, насколько больше времени потребуется для решения задачи для графа с вершинами по сравнению со временем, необходимым для графа с вершинами?
Если размер входных данных равен , затраченное время можно выразить как функцию от . Поскольку время, затраченное на различные входные данные одинакового размера, может быть разным, наихудшая временная сложность определяется как максимальное время, затраченное на все входные данные размера . Если является полиномом от , то говорят, что алгоритм является алгоритмом с полиномиальным временем . Тезис Кобэма утверждает, что задачу можно решить с помощью допустимого количества ресурсов, если она допускает алгоритм с полиномиальным временем.
Машина Тьюринга — это математическая модель общей вычислительной машины. Это теоретическое устройство, которое манипулирует символами, содержащимися на полоске ленты. Машины Тьюринга не предназначены для практической вычислительной технологии, а скорее для общей модели вычислительной машины — от продвинутого суперкомпьютера до математика с карандашом и бумагой. Считается, что если проблема может быть решена с помощью алгоритма, то существует машина Тьюринга, которая решает эту проблему. Действительно, это утверждение тезиса Чёрча-Тьюринга . Кроме того, известно, что все, что может быть вычислено на других моделях вычислений, известных нам сегодня, таких как машина RAM , игра Конвея «Жизнь » , клеточные автоматы , лямбда-исчисление или любой язык программирования, может быть вычислено на машине Тьюринга. Поскольку машины Тьюринга легко анализировать математически, и считается, что они столь же мощны, как и любая другая модель вычислений, машина Тьюринга является наиболее часто используемой моделью в теории сложности.
Для определения классов сложности используются многие типы машин Тьюринга, такие как детерминированные машины Тьюринга , вероятностные машины Тьюринга , недетерминированные машины Тьюринга , квантовые машины Тьюринга , симметричные машины Тьюринга и чередующиеся машины Тьюринга . Все они в принципе одинаково мощны, но когда ресурсы (такие как время или пространство) ограничены, некоторые из них могут быть мощнее других.
Детерминированная машина Тьюринга — это самая простая машина Тьюринга, которая использует фиксированный набор правил для определения своих будущих действий. Вероятностная машина Тьюринга — это детерминированная машина Тьюринга с дополнительным запасом случайных битов. Способность принимать вероятностные решения часто помогает алгоритмам решать проблемы более эффективно. Алгоритмы, которые используют случайные биты, называются рандомизированными алгоритмами . Недетерминированная машина Тьюринга — это детерминированная машина Тьюринга с дополнительной функцией недетерминизма, которая позволяет машине Тьюринга иметь несколько возможных будущих действий из заданного состояния. Один из способов рассмотрения недетерминизма заключается в том, что машина Тьюринга разветвляется на множество возможных вычислительных путей на каждом шаге, и если она решает задачу в любой из этих ветвей, говорят, что она решила задачу. Очевидно, что эта модель не должна быть физически реализуемой моделью, это просто теоретически интересная абстрактная машина, которая порождает особенно интересные классы сложности. Для примеров см. недетерминированный алгоритм .
В литературе было предложено много моделей машин, отличных от стандартных многоленточных машин Тьюринга , например, машины с произвольным доступом . Возможно, это удивительно, но каждая из этих моделей может быть преобразована в другую без предоставления какой-либо дополнительной вычислительной мощности. Время и потребление памяти этими альтернативными моделями могут различаться. [2] Общим для всех этих моделей является то, что машины работают детерминированно .
Однако некоторые вычислительные проблемы легче анализировать с точки зрения более необычных ресурсов. Например, недетерминированная машина Тьюринга — это вычислительная модель, которая может разветвляться для проверки множества различных возможностей одновременно. Недетерминированная машина Тьюринга имеет очень мало общего с тем, как мы физически хотим вычислять алгоритмы, но ее ветвление точно охватывает многие математические модели, которые мы хотим анализировать, так что недетерминированное время — очень важный ресурс при анализе вычислительных проблем.
Для точного определения того, что значит решить задачу, используя заданное количество времени и пространства, используется вычислительная модель, такая как детерминированная машина Тьюринга . Время, необходимое детерминированной машине Тьюринга для ввода, представляет собой общее количество переходов состояний или шагов, которые машина делает, прежде чем остановится и выдаст ответ («да» или «нет»). Говорят, что машина Тьюринга работает за время , если время, требуемое для каждого ввода длины, не превышает . Задача принятия решения может быть решена за время, если существует работающая за время машина Тьюринга, которая решает эту задачу. Поскольку теория сложности заинтересована в классификации задач на основе их сложности, мы определяем наборы задач на основе некоторых критериев. Например, набор задач, решаемых за время на детерминированной машине Тьюринга, обозначается как DTIME ( ).
Аналогичные определения можно сделать для требований к пространству. Хотя время и пространство являются наиболее известными ресурсами сложности, любую меру сложности можно рассматривать как вычислительный ресурс. Меры сложности очень обобщенно определяются аксиомами сложности Блюма . Другие меры сложности, используемые в теории сложности, включают сложность связи , сложность схемы и сложность дерева решений .
Сложность алгоритма часто выражается с помощью нотации «О большое» .
Лучшая , худшая и средняя сложность относятся к трем различным способам измерения временной сложности (или любой другой меры сложности) различных входных данных одинакового размера. Поскольку некоторые входные данные могут быть решены быстрее, чем другие, мы определяем следующие сложности:
Порядок от дешевого к дорогому следующий: наилучший, средний ( дискретного равномерного распределения ), амортизированный, наихудший.
Например, детерминированный алгоритм сортировки quicksort решает проблему сортировки списка целых чисел. Худший случай — когда опорная точка всегда является наибольшим или наименьшим значением в списке (поэтому список никогда не делится). В этом случае алгоритму требуется время O ( ). Если предположить, что все возможные перестановки входного списка равновероятны, среднее время, необходимое для сортировки, составляет . Лучший случай — когда каждая опорная точка делит список пополам, что также требует времени.
Чтобы классифицировать время вычислений (или аналогичные ресурсы, такие как потребление пространства), полезно продемонстрировать верхние и нижние границы максимального количества времени, требуемого наиболее эффективным алгоритмом для решения данной задачи. Сложность алгоритма обычно принимается как его наихудшая сложность, если не указано иное. Анализ конкретного алгоритма относится к области анализа алгоритмов . Чтобы показать верхнюю границу временной сложности задачи, нужно показать только, что существует конкретный алгоритм со временем выполнения не более . Однако доказать нижние границы гораздо сложнее, поскольку нижние границы делают утверждение обо всех возможных алгоритмах, решающих данную задачу. Фраза «все возможные алгоритмы» включает в себя не только алгоритмы, известные сегодня, но и любые алгоритмы, которые могут быть открыты в будущем. Чтобы показать нижнюю границу для задачи, необходимо показать, что ни один алгоритм не может иметь временную сложность ниже .
Верхние и нижние границы обычно указываются с использованием нотации big O , которая скрывает постоянные множители и меньшие члены. Это делает границы независимыми от конкретных деталей используемой вычислительной модели. Например, если , в нотации big O можно было бы написать .
Класс сложности — это набор проблем связанной сложности. Более простые классы сложности определяются следующими факторами:
Некоторые классы сложности имеют сложные определения, которые не вписываются в эту структуру. Таким образом, типичный класс сложности имеет следующее определение:
Но ограничение времени вычисления выше некоторой конкретной функцией часто дает классы сложности, которые зависят от выбранной модели машины. Например, язык может быть решен за линейное время на многоленточной машине Тьюринга, но обязательно требует квадратичного времени в модели одноленточной машины Тьюринга. Если мы допускаем полиномиальные вариации времени выполнения, тезис Кобэма-Эдмондса гласит, что «временные сложности в любых двух разумных и общих моделях вычислений полиномиально связаны» (Goldreich 2008, Глава 1.2). Это формирует основу для класса сложности P , который является набором задач принятия решений, решаемых детерминированной машиной Тьюринга за полиномиальное время. Соответствующий набор функциональных задач — FP .
Многие важные классы сложности могут быть определены путем ограничения времени или пространства, используемых алгоритмом. Некоторые важные классы сложности задач принятия решений, определенные таким образом, следующие:
Классы логарифмического пространства не учитывают пространство, необходимое для представления задачи.
Оказывается, PSPACE = NPSPACE и EXPSPACE = NEXPSPACE по теореме Сэвича .
Другие важные классы сложности включают BPP , ZPP и RP , которые определяются с помощью вероятностных машин Тьюринга ; AC и NC , которые определяются с помощью булевых схем; и BQP и QMA , которые определяются с помощью квантовых машин Тьюринга. #P — важный класс сложности задач подсчета (не задач принятия решений). Такие классы, как IP и AM, определяются с помощью интерактивных систем доказательств . ALL — класс всех задач принятия решений.
Для классов сложности, определенных таким образом, желательно доказать, что ослабление требований к (скажем) времени вычислений действительно определяет больший набор проблем. В частности, хотя DTIME( ) содержится в DTIME( ), было бы интересно узнать, является ли включение строгим. Для требований времени и пространства ответ на такие вопросы дается теоремами об иерархии времени и пространства соответственно. Они называются теоремами об иерархии, потому что они индуцируют надлежащую иерархию для классов, определенных ограничением соответствующих ресурсов. Таким образом, существуют пары классов сложности, такие, что один надлежащим образом включен в другой. Выведя такие надлежащие включения множеств, мы можем перейти к количественным утверждениям о том, насколько больше дополнительного времени или пространства необходимо для увеличения количества решаемых задач.
Точнее, теорема об иерархии времени утверждает, что .
Теорема о пространственной иерархии утверждает, что .
Теоремы об иерархии времени и пространства формируют основу для большинства результатов разделения классов сложности. Например, теорема об иерархии времени говорит нам, что P строго содержится в EXPTIME, а теорема об иерархии пространства говорит нам, что L строго содержится в PSPACE.
Многие классы сложности определяются с использованием концепции редукции. Редукция — это преобразование одной проблемы в другую. Она охватывает неформальное понятие проблемы, которая не сложнее другой проблемы. Например, если проблема может быть решена с помощью алгоритма для , не сложнее , и мы говорим, что сводится к . Существует много различных типов редукций, основанных на методе редукции, таких как редукции Кука, редукции Карпа и редукции Левина, и границе сложности редукций, таких как редукции за полиномиальное время или редукции с использованием логарифмического пространства .
Наиболее часто используемая редукция — это редукция за полиномиальное время. Это означает, что процесс редукции занимает полиномиальное время. Например, задачу возведения в квадрат целого числа можно свести к задаче умножения двух целых чисел. Это означает, что алгоритм умножения двух целых чисел можно использовать для возведения в квадрат целого числа. Действительно, это можно сделать, подав одинаковые входные данные на оба входа алгоритма умножения. Таким образом, мы видим, что возведение в квадрат не сложнее умножения, поскольку возведение в квадрат можно свести к умножению.
Это мотивирует концепцию проблемы, которая является сложной для класса сложности. Проблема является сложной для класса проблем , если каждая проблема из может быть сведена к . Таким образом, ни одна проблема из не является сложной, чем , поскольку алгоритм для позволяет нам решить любую проблему из . Понятие сложных проблем зависит от типа используемой редукции. Для классов сложности, больших, чем P, обычно используются редукции за полиномиальное время. В частности, набор проблем, которые являются сложными для NP, — это набор NP-сложных проблем.
Если задача находится в и сложна для , то считается полной для . Это означает, что является самой сложной задачей в . (Поскольку многие задачи могут быть одинаково сложны, можно сказать, что это одна из самых сложных задач в .) Таким образом, класс NP-полных задач содержит самые сложные задачи в NP, в том смысле, что они, скорее всего, не находятся в P. Поскольку задача P = NP не решена, возможность свести известную NP-полную задачу, , к другой задаче, , будет означать, что не существует известного решения за полиномиальное время для . Это происходит потому, что решение за полиномиальное время для даст решение за полиномиальное время для . Аналогично, поскольку все задачи NP можно свести к набору , нахождение NP-полной задачи, которая может быть решена за полиномиальное время, будет означать, что P = NP. [3]
Класс сложности P часто рассматривается как математическая абстракция, моделирующая те вычислительные задачи, которые допускают эффективный алгоритм. Эта гипотеза называется тезисом Кобэма–Эдмондса . С другой стороны, класс сложности NP содержит много проблем, которые люди хотели бы решить эффективно, но для которых не известен эффективный алгоритм, например, проблема булевой выполнимости , проблема гамильтонового пути и проблема покрытия вершин . Поскольку детерминированные машины Тьюринга являются особыми недетерминированными машинами Тьюринга, легко заметить, что каждая проблема в P также является членом класса NP.
Вопрос о том, равно ли P NP, является одним из самых важных открытых вопросов в теоретической информатике из-за широких последствий решения. [3] Если ответ да, то можно показать, что многие важные проблемы имеют более эффективные решения. К ним относятся различные типы задач целочисленного программирования в исследовании операций , многие задачи в логистике , предсказание структуры белка в биологии , [5] и способность находить формальные доказательства теорем чистой математики . [6] Задача P против NP является одной из задач Премии тысячелетия, предложенных Математическим институтом Клэя . За решение задачи предусмотрена премия в размере 1 000 000 долларов США. [7]
Ладнер показал, что если то существуют задачи из , которые не являются ни в , ни -полными. [4] Такие задачи называются NP-промежуточными задачами. Задача изоморфизма графов , задача дискретного логарифмирования и задача факторизации целых чисел являются примерами задач, которые считаются NP-промежуточными. Они являются одними из немногих задач NP, о которых неизвестно, находятся ли они в или являются -полными.
Проблема изоморфизма графов — это вычислительная проблема определения того, являются ли два конечных графа изоморфными . Важной нерешенной проблемой в теории сложности является то, является ли проблема изоморфизма графов в , -полной или NP-промежуточной. Ответ неизвестен, но считается, что проблема по крайней мере не NP-полная. [8] Если изоморфизм графов является NP-полным, иерархия полиномиального времени схлопывается до своего второго уровня. [9] Поскольку широко распространено мнение, что полиномиальная иерархия не схлопывается ни до какого конечного уровня, считается, что изоморфизм графов не является NP-полным. Лучший алгоритм для этой проблемы, созданный Ласло Бабаем и Юджином Люксом, — это время выполнения для графов с вершинами, хотя некоторые недавние работы Бабая предлагают некоторые потенциально новые перспективы по этому вопросу. [10]
Задача факторизации целых чисел — это вычислительная задача определения простого множителя заданного целого числа. Формулируя ее как задачу принятия решений, это задача определения, имеет ли входной сигнал простой множитель, меньший . Эффективный алгоритм факторизации целых чисел неизвестен, и этот факт лежит в основе нескольких современных криптографических систем, таких как алгоритм RSA . Задача факторизации целых чисел находится в и в (и даже в UP и co-UP [11] ). Если задача является -полной, иерархия полиномиального времени схлопнется до своего первого уровня (т. е. будет равна ). Самым известным алгоритмом факторизации целых чисел является общее решето числового поля , которому требуется время [12] для факторизации нечетного целого числа . Однако самый известный квантовый алгоритм для этой задачи, алгоритм Шора , работает за полиномиальное время. К сожалению, этот факт мало что говорит о том, где находится проблема относительно неквантовых классов сложности.
Многие известные классы сложности, как предполагается, неравны, но это не доказано. Например , , но возможно, что . Если не равно , то не равно ни одному из них. Поскольку существует много известных классов сложности между и , таких как , , , , , , и т. д., возможно, что все эти классы сложности свернутся в один класс. Доказательство того, что любой из этих классов неравно, станет крупным прорывом в теории сложности.
В том же ключе, класс, содержащий дополнительные проблемы (т.е. проблемы с ответами «да» / «нет» в обратном порядке) проблем. Считается [13] , что не равно ; однако это еще не доказано. Ясно, что если эти два класса сложности не равны, то не равно , так как . Таким образом, если бы мы имели откуда .
Аналогично, неизвестно, содержится ли (множество всех задач, которые могут быть решены в логарифмическом пространстве) строго в или равно . Опять же, между ними есть много классов сложности, таких как и , и неизвестно, являются ли они различными или равными классами.
Подозревается, что и равны. Однако в настоящее время он открыт, если .
Проблема, которая теоретически может быть решена, но для ее решения требуются непрактичные и ограниченные ресурсы (например, время), называетсяНеразрешимая проблема .[14]И наоборот, проблема, которая может быть решена на практике, называетсяtractable problem , буквально «проблема, с которой можно справиться». Терминinfeasible(буквально «невозможно») иногда используется взаимозаменяемо сintractable,[15]хотя это рискует спутать сдопустимым решениемвматематической оптимизации.[16]
Решаемые проблемы часто отождествляются с проблемами, имеющими полиномиальное время решения ( , ); это известно как тезис Кобэма–Эдмондса . Проблемы, которые известны как нерешаемые в этом смысле, включают те, которые являются EXPTIME -трудными. Если не то же самое, что , то NP-трудные проблемы также являются нерешаемыми в этом смысле.
Однако эта идентификация неточна: решение с полиномиальным временем с большой степенью или большим ведущим коэффициентом растет быстро и может быть непрактичным для практических задач размера; наоборот, решение с экспоненциальным временем, которое растет медленно, может быть практичным при реалистичных входных данных, или решение, которое занимает много времени в худшем случае, может занять короткое время в большинстве случаев или в среднем случае и, таким образом, все еще быть практичным. Утверждение, что проблема не в , не означает, что все большие случаи проблемы сложны или даже что большинство из них сложны. Например, было показано, что проблема принятия решения в арифметике Пресбургера не находится в , однако были написаны алгоритмы, которые решают эту проблему за разумное время в большинстве случаев. Аналогично, алгоритмы могут решить NP-полную задачу о рюкзаке в широком диапазоне размеров за время, меньшее, чем квадратичное, и решатели SAT обычно обрабатывают большие экземпляры NP-полной задачи булевой выполнимости .
Чтобы понять, почему алгоритмы с экспоненциальным временем обычно непригодны на практике, рассмотрим программу, которая выполняет операции перед остановкой. Для небольших , скажем, 100, и предположив для примера, что компьютер выполняет операции каждую секунду, программа будет работать около лет, что того же порядка, что и возраст Вселенной . Даже с гораздо более быстрым компьютером программа будет полезна только для очень маленьких случаев, и в этом смысле неразрешимость проблемы несколько независима от технологического прогресса. Однако алгоритм с экспоненциальным временем, который выполняет операции, практичен, пока не станет относительно большим.
Аналогично, алгоритм полиномиального времени не всегда практичен. Если его время выполнения, скажем, , то неразумно считать его эффективным, и он по-прежнему бесполезен, за исключением небольших случаев. Действительно, на практике даже алгоритмы или часто непрактичны для реалистичных размеров задач.
Непрерывная теория сложности может относиться к теории сложности проблем, которые включают непрерывные функции, аппроксимируемые дискретизациями, как изучается в численном анализе . Одним из подходов к теории сложности численного анализа [17] является информационная сложность .
Непрерывная теория сложности может также относиться к теории сложности использования аналоговых вычислений , которая использует непрерывные динамические системы и дифференциальные уравнения . [18] Теория управления может рассматриваться как форма вычислений, а дифференциальные уравнения используются при моделировании непрерывных и гибридных дискретно-непрерывных систем. [19]
Ранним примером анализа сложности алгоритма является анализ времени выполнения алгоритма Евклида, выполненный Габриэлем Ламе в 1844 году.
До того, как началось фактическое исследование, явно посвященное сложности алгоритмических проблем, различными исследователями были заложены многочисленные основы. Наиболее влиятельным среди них было определение машин Тьюринга Аланом Тьюрингом в 1936 году, которое оказалось очень надежным и гибким упрощением компьютера.
Начало систематических исследований вычислительной сложности приписывается основополагающей статье 1965 года «О вычислительной сложности алгоритмов» Юриса Хартманиса и Ричарда Э. Стернса , в которой были изложены определения временной и пространственной сложности , а также доказаны теоремы об иерархии. [20] Кроме того, в 1965 году Эдмондс предложил считать «хорошим» алгоритмом тот, время выполнения которого ограничено полиномом от размера входных данных. [21]
Более ранние работы, изучающие проблемы, решаемые машинами Тьюринга с определенными ограниченными ресурсами, включают [20] определение линейных ограниченных автоматов Джона Майхилла (Myhill 1960), исследование элементарных множеств Рэймонда Смаллиана (1961), а также работу Хисао Ямады [22] о вычислениях в реальном времени (1962). Несколько ранее Борис Трахтенброт (1956), пионер в этой области из СССР, изучал другую определенную меру сложности. [23] Как он вспоминает:
Однако [мой] первоначальный интерес [к теории автоматов] все больше отодвигался в сторону в пользу вычислительной сложности, захватывающего слияния комбинаторных методов, унаследованных от теории переключений , с концептуальным арсеналом теории алгоритмов. Эти идеи пришли мне в голову ранее, в 1955 году, когда я придумал термин «сигнализирующая функция», который в настоящее время широко известен как «мера сложности». [24]
В 1967 году Мануэль Блюм сформулировал набор аксиом (теперь известных как аксиомы Блюма ), определяющих желаемые свойства мер сложности на множестве вычислимых функций, и доказал важный результат, так называемую теорему об ускорении . Область начала процветать в 1971 году, когда Стивен Кук и Леонид Левин доказали существование практически значимых задач, которые являются NP-полными . В 1972 году Ричард Карп вывел эту идею на новый уровень в своей знаковой статье «Сводимость среди комбинаторных задач», в которой он показал, что 21 разнообразная комбинаторная и теоретико-графовая задача, каждая из которых печально известна своей вычислительной неразрешимостью, является NP-полной. [25]
![{\displaystyle O(e^{\left({\sqrt[{3}]{\frac {64}{9}}}\right){\sqrt[{3}]{(\log n)}}{\sqrt[{3}]{(\log \log n)^{2}}}})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d50912fbf223d0bbadd2a028262414397fbee1a9)
