Класс P


Класс P

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

Содержание

Определения

Формальное определение

Алгоритм отождествляется с детерминированной машиной Тьюринга, которая вычисляет ответ по данному на входную ленту слову из входного алфавита \Sigma. Временем работы алгоритма T_M(x) при фиксированном входном слове x называется количество рабочих тактов машины Тьюринга от начала до остановки машины. Сложностью функции f: \Sigma^* \to \Sigma^*, вычисляемой некоторой машиной Тьюринга, называется функция C: \mathbb N \to \mathbb N, зависящая от длины входного слова и равная максимуму времени работы машины по всем входным словам фиксированной длины:

C_M (n) = \max\limits_{x: |x| = n} T_M (x).

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

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

Более узкое определение

Иногда под классом P имеют в виду более узкий класс функций, а именно класс предикатов (функций f: \Sigma^* \to \{ 0,\, 1\}). В таком случае языком L, который распознаёт данный предикат, называется множество слов, на которых предикат равен 1. Языками класса P называются языки, для которых существуют распознающие их предикаты класса P. Очевидно, что если языки L_1 и L_2 лежат в классе P, то и их объединение, пересечение и дополнения также лежат в классе P.

Включения класса P в другие классы

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

Уже более 30 лет остаётся нерешённой задача о равенстве классов P и NP. Если они равны, то любую задачу из класса NP можно будет решить быстро (за полиномиальное время). Однако научное сообщество склоняется в сторону отрицательного ответа на этот вопрос. Кроме того, не доказана и строгость включения в более широкие классы, например, в PSPACE, но равенство P и PSPACE выглядит на данный момент очень сомнительно.

Примеры задач

Задачи, принадлежащие классу P

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

Задачи, принадлежность которых классу P неизвестна

Существует много задач, для которых не найдено полиномиального алгоритма, но не доказано, что его не существует. Соответственно, неизвестно, принадлежат ли такие задачи классу P. Вот некоторые из них:

  1. Задача коммивояжёра (а также все остальные NP-полные задачи). Полиномиальное решение этой задачи равносильно установлению равенства классов P и NP.
  2. Разложение числа на простые множители.
  3. Дискретное логарифмирование в конечном поле.
  4. Задача о скрытой подгруппе с n образующими.
  5. Дискретное логарифмирование в аддитивной группе точек на эллиптической кривой.

Практическое значение

Поскольку часто приходится вычислять значения функций на входных данных большого объёма, нахождение полиномиальных алгоритмов для вычисления функций является очень важной задачей. Считается, что вычислять функции, не лежащие в классе P, заметно сложнее, чем лежащие. Большинство алгоритмов, лежащих в классе P, имеют сложность, не превосходящую многочлен небольшой степени от размера входных данных. Например, стандартный алгоритм перемножения матриц требует n3 умножений (хотя существуют и более быстрые алгоритмы, например, алгоритм Штрассена). Степень многочлена редко бывает большой. Один из таких случаев — предложенный в 2002 году индийскими математиками тест Агравала — Каяла — Саксены, выясняющий, является ли число n простым, за O(log6n) операций.

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Класс P" в других словарях:

  • класс — класс, а …   Русский орфографический словарь

  • класс — класс/ …   Морфемно-орфографический словарь

  • КЛАСС — (в логике и математике) 1) понятие, присущее всем элементам некоторой совокупности объектов; 2) совокупность выделенных по некоторому признаку объектов, мыслимая как целое. Понятие К. (множества) обычно относят к числу простейших, неопределяемых… …   Философская энциклопедия

  • Класс! — Класс! …   Википедия

  • КЛАСС — (лат. classis порядок.). 1) разряд однородных предметов. 2) собрание учеников для учебных занятий, а также помещение и самое время, назначенное для урока. 3) степень в государственной службе. Словарь иностранных слов, вошедших в состав русского… …   Словарь иностранных слов русского языка

  • класс — сущ., м., употр. часто Морфология: (нет) чего? класса, чему? классу, (вижу) что? класс, чем? классом, о чём? о классе; мн. что? классы, (нет) чего? классов, чему? классам, (вижу) что? классы, чем? классами, о чём? о классах 1. Классом называют… …   Толковый словарь Дмитриева

  • КЛАСС — КЛАСС, [ас] класса, м. [латин. classis]. 1. Социальная группа, часть общества, объединенная общностью интересов вследствие одинакового отношения к средствам производства и противостоящая другим социальным группам в силу противоположности… …   Толковый словарь Ушакова

  • КЛАСС! — КЛАСС! …   Википедия

  • КЛАСС — (class) Оксфордский словарь английского языка дает следующее определение класса: Разделение общества или порядок в обществе согласно статусу; разряд, категория общества . Но это определение класса столь же разъясняет, сколь и вносит путаницу.… …   Политология. Словарь.

  • класс — а; м. [от лат. classis разряд] 1. (чего) В научной терминологии: совокупность, группа предметов или явлений с общими признаками; разряд, категория. К. млекопитающих. К. земноводных. К. двудольных растений. Плавать на судах различных классов.… …   Энциклопедический словарь

  • класс — См. разряд …   Словарь синонимов

Книги

Другие книги по запросу «Класс P» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.