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

Обновлено: 30.06.2024

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

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

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

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

I. Общие свойства сигнализирующих операторов, аксиоматическая теория С. в. Для наиболее употребительных классов автоматов, вычисляющих все частично рекурсивные ф-ции (напр., для машин Тьюринга), и для широкого класса сигнализирующих операторов а (21, а), включающих, напр., время вычисления и объем внеш. памяти машин Тьюринга, установлены следующие фундаментальные факты (далее, если не сделана оговорка, все ф-ции считаются общерекурсивными). Во-первых, существуют сколь угодно сложно вычислимые ф-ции (предикаты), точнее, для каждой ф-ции существует предикат g такой, что, если автомат 21 вычисляет g, то а почти для всех а. Во-вторых, существуют предикаты, любое вычисление которых может быть сколь угодно сильно улучшено для всех достаточно больших значений аргумента, точнее, для каждой ф-ции существует предикат g, такой, что если 21 вычисляет g, то найдется , вычисляющий g и такой, что почти всегда

II. Свойства мер и связь между различными мерами для фиксированных классов автоматов. Рассмотрим, напр., класс обычных одноленточных машин Тьюринга. В качестие меры С. в. иозьмем временную сигнализирующую ф-цию t — время работы на аргументе а. Сформулируем некоторые результаты и терминах распознаиаиия (представления) языков (см. Поведение автоматов). Высказыиание «язык распознается за время понимают так: существует машина, распознающая этот язык, для которой временная сигнализирующая ф-ция на словах длины не больше . Если язык распознается за иремя то он распознается за время для всякого Поэтому оценки даются с точностью до С определенного порядка. Может оказаться, что какой-то язык распознается за время, по порядку равное , и не распознается за время, по порядку меньше . Тогда наилучшее иозможное для этого языка время вычисления точной иременной сигнализирующей ф-цией). Как отмечено и разделе I, такое бывает не исегда. Для языка, состоящего из симметричных слои, показано, что наилучшее время вычисления имеет порядок Построена серия языкои, точные иременные сигнализирующие ф-ции которых лежат между . Доказано, что между нет точных иременных сигнализирующих ф-ций. Сиязь между временной и емкостной сигнализирующими ф-циями устанаилииает следующая теорема: пусть язык распознается за время . Если то этот язык распознается с емкостной сигнализирующей ф-цией, не большей . Аналогичные и другие вопросы изучались для разных типов машин Тьюринга, машин Минского (машин со счетчиками), автоматои с магазинной памятью (см. Автомат магазинный) и др.

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

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

IV. Связь между сложностными характеристиками классов ф-ций и языков и их структурными, логическими, алгебраическими и т. п. свойствами. Для некоторых известных классои рекурсивных функций и языкои удается получить точную характеристику и сложностных терминах. Напр., класс примитивно-рекурсивных ф-ций состоит и точности из тех ф-ций, С. и. которых ограничена некоторой рекурсинной ф-цией; класс языков непосредстиенно состаиляющих соипадает с классом языкои, распознаиаемых недетерминироианными машинами Тьюринга с емкостной сигнализирующей функцией

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

V. С. в. конкретных классов ф-ций и языков.

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

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

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

VII. Меры сложности и подходы, учитывающие С. в. и сложность описания алгоритма.

В качестве одной из таких мер рассматривается, напр., произведение числа внутр. состояний машин Тьюринга на сигнализирующую ф-цию. Изучается зависимость сложности записи алгоритмов, вычисляющих конечные последовательности, от времени их работы. При наложении эффективного ограничения на время работы сложность алгоритмов, удовлетворяющих этому ограничению, может резко возрасти. Лит.: Трахтенброт Б. А. Сложность алгоритмов и вычислений. Новосибирск, 1967 [библиогр. с. 255—258]; Фишер П. Многоленточные и бесконечные автоматы. В кн.: Кибернетический сборник. Новая серия, в. 5. М., 1968; Проблемы математической логики. Сложность алгоритмов и классы вычислимых функций. М., 1970. В. Н. Агафонов.

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

Содержание

Глава 1 Ведение 1-3
Временная и пространственная сложности 1-4
Асимптотическая сложность 1-5
Классы сложности 1-6
Отношения между классами 1-8
Глава 2 Заключение. 2-10
Глава 3 Список использованной литературы. 3-11

Работа содержит 1 файл

РЕФЕРАТ.docx

Глава 1 Ведение 1-3

Временная и пространственная сложности 1-4

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

Классы сложности 1-6

Отношения между классами 1-8

Глава 2 Заключение. 2-10

Глава 3 Список использованной литературы. 3-11

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

В частности, теория сложности вычислений определяет NP-полные задачи , которые недетерминированная машина Тьюринга может решить за полиномиальное время , тогда как для детерминированной машины Тьюринга полиномиальный алгоритм неизвестен . Обычно это сложные проблемы оптимизации, например, задача коммивояжера .

Временная и пространственная сложности

Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения и объём необходимой памяти) в зависимости от размера входа и выхода.

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

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

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

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

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

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

В теории сложности вычислений сведение — преобразование одной задачи к другой. В общем случае, если у нас есть алгоритм, преобразующий экземпляры задачи P₁ в экземпляры задачи P₂, которые имеют тот же ответ (да/нет), то говорят, что P₁сводится к P₂. Таким образом, сводимость — это отношение между двумя задачами. С помощью такой связи могут быть доказаны вычислимость задачи или ее принадлежность тому или иному классу сложности .

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

Класс сложности — это множество задач распознавания, для решения которых существуют алгоритмы, схожие по вычислительной сложности. Два важных представителя:

В теории алгоритмов классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Говоря более узко, классы сложности — это множества предикатов ( функций , получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов.

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

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

Проблема равенства классов P и NP

Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. Математический институт Клэя включил эту проблему в список проблем тысячелетия , предложив награду размером в один миллион долларов США за её решение.

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

Классом сложности X называется множество предикатов P(x), вычислимых на машинах Тьюринга и использующих для вычисления O (f(n)) ресурса, где n — длина слова x.

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

Кроме того, многие классы могут также быть описаны в терминах математичес кой логики или теории игр .

Классы принято обозначать прописными буквами. Дополнение к классу C (то есть класс языков, дополнения которых принадлежат C) обозначается co-C.

Все классы сложности находятся в иерархическом отношении: одни включают в себя другие. Однако про большинство включений неизвестно, являются ли они строгими. Одна из наиболее известных открытых проблем в этой области — равенство классов P и NP . Если это предположение верно (в чём большинство учёных сомневается), то представленная справа иерархия классов сильно свернётся. На данный момент наиболее распространённой является гипотеза о не вырожденности иерархии (то есть все классы различны). Кроме того, известно, что EXPSPACE не равен классу PSPACE .

Теория вычислимости берёт свое начало от диссертации Тьюринга ( 1936 ), в которой он ввел понятие абстрактной вычислительной машины, получившей впоследствии его имя, и доказал фундаментальную теорему о неразрешимости задачи о её остановке .

В настоящее время исследования по теории вычислимости активно ведутся во всех странах мира. Россия всегда была одним из мировых центров исследований по теории вычислимости и её приложениям. Эти исследования берут начало от ранних работ Маркова и Мальцева по теории алгоритмов и её связям с алгеброй , ознаменовались решением проблемы Поста Мучником. Эти исследования сегодня продолжаются на очень высоком уровне во многих научных центрах России (школа Ершова в Новосибирске, школа Арсланова в Казани) и других стран бывшего Советского Союза (Алма-Ата, Казахстан).

2. Угринович Н.Д. Информатика и информационные технологии. Учебник для 10-11 классов. – М.: БИНОМ. Лаборатория знаний, 2005.

3. Угринович Н.Д. Практикум по информатике и информационным технологиям: Учебное пособие для общеобразовательных учреждений/ Н.Д.Угринович, Л.Л.Босова, Н.И.Михайлова. – 4-е изд. – М.: БИНОМ. Лаборатория знаний, 2006. – 394с.: ил.

В частности, теория сложности вычислений определяет NP-полные задачи, которые недетерминированная машина Тьюринга может решить за полиномиальное время, тогда как для детерминированной машины Тьюринга полиномиальный алгоритм неизвестен. Обычно это сложные проблемы оптимизации, например, задача коммивояжера.

Содержание

Временная и пространственная сложности

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

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

Обозначение	Интуитивное объяснение	Определение
$f(n) \in O(g(n))$	f ограничена сверху функцией g (с точностью до постоянного множителя) асимптотически	или
$f(n) \in \Omega(g(n))$	f ограничена снизу функцией g (с точностью до постоянного множителя) асимптотически
$f(n) \in \Theta(g(n))$	f ограничена снизу и сверху функцией g асимптотически
$f(n) \in o(g(n))$	g доминирует над f асимптотически
$f(n) \in \omega(g(n))$	f доминирует над g асимптотически
$f(n) \sim g(n)\!$	f эквивалентна g асимптотически	$\lim_<n \to \infty>\frac = 1$

Примеры

Замечания

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

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

Эффективные, но сложные алгоритмы могут быть нежелательными, если готовые программы будут поддерживать лица, не участвующие в написании этих программ.

В численных алгоритмах точность и устойчивость алгоритмов не менее важны, чем их временная эффективность.

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

Класс P

Класс NP

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

Проблема равенства классов P и NP

Вопрос о равенстве этих двух классов считается одной из самых сложных открытых проблем в области теоретической информатики. Математический институт Клэя включил эту проблему в список проблем тысячелетия, предложив награду размером в один миллион долларов США за её решение.

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

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

Содержание

Вычислительные проблемы

Экземпляры задач

Представление задачи

При рассмотрении вычислительных задач описанием экземпляра задачи является строка над алфавитом. Как правило, алфавит берется бинарным(т. е. множество ). Различные математические объекты должны быть соответствующим образом закодированы. Так, например, целые числа могут быть представлены в двоичной системе счисления, и графы могут быть закодированы непосредственно через их матрицы смежности или через их кодирование списков смежности в двоичной системе.

Задачи распознавания

Задачи поиска

Измерение сложности

Теория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, чётко описывать их поведение (время исполнения, объём необходимой памяти и т.д.) в зависимости от размера входа и выхода.

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

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

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

Сложность определяется исходя из вычислительной модели, в которой проводят вычисления.

Вычислительные модели

Существует множество различных моделей вычислений: машина Поста, машина Минского, лямбда-исчисление, частично рекурсивные функции, нормальные алгоритмы Маркова, машины с произольным доступом к памяти (RAM машины) и др. Упомянем лишь наиболее популярную вычислительную модель — машину Тьюринга.

Машина Тьюринга

Маши́на Тью́ринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.

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

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

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

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара (ленточный символ — состояние), для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Модель машины Тьюринга допускает различные расширения. Можно рассматривать машины Тьюринга с произвольным числом лент и многомерными лентами с различными ограничениями; машины, использующие источник случайности.

Машина Тьюринга является одной из основных моделей вычисления в теории сложности.

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

Классами сложности называются множества вычислительных задач, примерно одинаковых по сложности вычисления. Существуют классы сложности языков и функциональные классы сложности. Класс сложности языков — это множество предикатов (функций, получающих на вход слово и возвращающих ответ 0 или 1), использующих для вычисления примерно одинаковые количества ресурсов. Понятие функционального класса сложности аналогично, за исключением того, что это не множество предикатов, а множество функций. В теории сложности, по умолчанию, класс сложности — это класс сложности языков. Типичное определение класса сложности выглядит так:

Кроме того, многие классы могут также быть описаны в терминах математической логики или теории игр.

Классы принято обозначать прописными буквами. Дополнение к классу C (то есть класс языков, дополнения которых принадлежат C) обозначается co-C.

Класс P

Класс P (от англ. polynomial) — множество задач распознавания, которые могут быть решены на детерминированной машине Тьюринга за полиномиальное от длины входа время. Аналогично, для задач поиска определяется класс FP (от англ. functional polynomial).

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

Если для функции f существует машина Тьюринга M такая, что для некоторого числа c и достаточно больших n, то говорят, что она принадлежит классу FP, или полиномиальна по времени.

Класс P является одним из фундаментальных в теории сложности вычислений.

Класс NP

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

Класс NP включает в себя класс P.

Открытые проблемы

В теории сложности вычислений существует множество нерешенных проблем, в основном они касаются вопросов разделения или вложенности тех или иных классов сложности. Одним из таких вопросов является проблема равенства классов P и NP.

Проблема равенства классов P и NP

В конечном счете проблема равенства классов P и NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время)?

Из определения классов P и NP сразу вытекает следствие: . Однако до сих пор ничего не известно о строгости этого включения, т.е. существует ли алгоритм, лежащий в NP, но не лежащий в P. Если такого алгоритма не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что сулит огромную выгоду с вычислительной точки зрения. Сейчас самые сложные NP-задачи (так называемые NP-полные задачи) можно решить за экспоненциальное время, что почти всегда неприемлемо.

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

Читайте также: