Клас складності P

Клас складності P (англ. Complexity class P) — клас задач, що можна розв'язати алгоритмами з поліноміальним часом.

Формальне визначення

Алгоритмом з поліноміальним часом називається такий алгоритм, час роботи якого (тобто, кількість елементарних двійкових операцій, необхідних для його виконання на детермінованій машині Тюринга) на вхідному рядку довжиною $l$ обмежено згори деяким поліномом $P(l)$ .[1]

Задачі, що можна розв'язати алгоритмом з поліноміальним часом належать до класу задач складності P.

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

Машина Тюринга $M$ має часову складність (або час роботи) $T(n)$ , якщо для довільного входу $w$ довжини $n$ , не залежно від результату машина $M$ зупиниться після виконання щонайбільше $T(n)$ кроків.

Деяка мова $L$ належить до класу складності P, якщо існує поліноміальне $T(n)$ таке, що мова $L$ розпізнається деякою детермінованою машиною Тюринга $M$ ( $L=L(M)$ ) з часовою складністю $T(n)$ .[2]

Практичне значення

Оскільки часто доводиться обчислювати значення функцій на вхідних даних великого обсягу, знаходження поліноміальних алгоритмів для обчислення функцій є дуже важливим завданням. Вважається, що обчислювати функції, які не лежать у класі $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 виглядає нині дуже сумнівно.

Приклади

Стандартний алгоритм множення матриць вимагає n³ операцій множення (хоча існують більш швидкі алгоритми, які теж мають поліноміальну швидкість, як, наприклад, алгоритм Штрассена).
Степінь многочлена рідко буває великим. Один з таких випадків — запропонований в 2002 індійськими математиками тест Агравала — Каяла — Сакса, який з'ясовує, чи є число n простим, за O(log⁶n) операцій.

Завдання, приналежність яких класу P невідома

Існує багато задач, для яких не знайдено поліноміального алгоритму, але не доведено, що його не існує. Відповідно, невідомо, належать такі завдання класу $P$ . Ось деякі з них:

Задача комівояжера (а також всі інші $NP$ -повні задачі). Поліноміальне розв'язання цієї задачі рівносильне встановленню рівності класів P і NP
Розкладання числа на прості множники
Дискретне логарифмування в скінченному полі
Задача про приховану підгрупу з $n$ твірними
Дискретне логарифмування в адитивній групі точок еліптичної кривої

Примітки

Рейнгольд, Нивергельт Ю., Део Н. (1980). Комбинаторные Алгоритмы (рос.). Москва: Мир. с. 442—443.
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages and Computation (англ.) (вид. 2-ге). Addison-Wesley. ISBN 0-201-44124-1.

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Рейнгольд, Нивергельт Ю., Део Н. (1980). Комбинаторные Алгоритмы (рос.). Москва: Мир. с. 442—443.

[2] John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages and Computation (англ.) (вид. 2-ге). Addison-Wesley. ISBN 0-201-44124-1.