Клас складності P (англ.Complexity class P) — клас задач, що можна розв'язати алгоритмами з поліноміальним часом.
Формальне визначення
Алгоритмом з поліноміальним часом називається такий алгоритм, час роботи якого (тобто, кількість елементарних двійкових операцій, необхідних для його виконання на детермінованій машині Тюринга) на вхідному рядку довжиною обмежено згори деяким поліномом.[1]
Задачі, що можна розв'язати алгоритмом з поліноміальним часом належать до класу задач складності P.
Машина Тюринга має часову складність (або час роботи) , якщо для довільного входу довжини , не залежно від результату машина зупиниться після виконання щонайбільше кроків.
Деяка мова належить до класу складності P, якщо існує поліноміальне таке, що мова розпізнається деякою детермінованою машиною Тюринга () з часовою складністю .[2]
Практичне значення
Оскільки часто доводиться обчислювати значення функцій на вхідних даних великого обсягу, знаходження поліноміальних алгоритмів для обчислення функцій є дуже важливим завданням. Вважається, що обчислювати функції, які не лежать у класі , помітно складніше, ніж лежать. Більшість алгоритмів, що лежать в класі , мають складність, яка не перевершує многочлен в невеликій мірі від розміру вхідних даних.
Вужче визначення
Іноді під класом P мають на увазі вужчий клас функцій, а саме клас предикатів (функцій ). Тоді мова, що розпізнає даний предикат, називається множиною слів, де предикат дорівнює 1. Мовами класу P називаються мови, для яких існують розпізнавальні їх предикати класу P. Очевидно, якщо мови і лежать у класі P, то і їх об'єднання, перетин та доповнення також лежать в класі P[джерело?].
Включення класу P в інші класи
Клас P є одним з найвужчих класів складності. Алгоритми, що належать йому, належать також класу NP, класу BPP (як допускають поліноміальну реалізацію з нульовою помилкою), класу PSPACE (т. к. зона роботи на машині Тюрінга завжди менше часу), класу P/Poly (для доказу цього факту використовується поняття протоколу роботи машини, який переробляється в булеву схему поліноміального розміру)[джерело?].
Вже понад 30 років залишається невирішеною задача про рівність класів P і NP. Якщо вони рівні, то будь-яке завдання з класу NP можна буде вирішити швидко (за поліноміальний час). Однак наукове товариство схиляється в бік негативної відповіді на це питання. Крім того, не доведено і строгість включення до ширших класів, наприклад, в PSPACE, але рівність P і PSPACE виглядає нині дуже сумнівно.
Приклади
Стандартний алгоритм множення матриць вимагає n3 операцій множення (хоча існують більш швидкі алгоритми, які теж мають поліноміальну швидкість, як, наприклад, алгоритм Штрассена).
Степінь многочлена рідко буває великим. Один з таких випадків — запропонований в 2002 році індійськими математиками тест Агравала — Каяла — Сакса, який з'ясовує, чи є число nпростим, за O(log6n) операцій.
Завдання, приналежність яких класу P невідома
Існує багато задач, для яких не знайдено поліноміального алгоритму, але не доведено, що його не існує. Відповідно, невідомо, належать такі завдання класу . Ось деякі з них: