WikiSort.ru - Не сортированное

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

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

${\displaystyle C_{M}(n)=\max \limits _{x:|x|=n}T_{M}(x)}$ .

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

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

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

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

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

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

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

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

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