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

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

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

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

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

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

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

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

Дивіться також

• Клас складності NP
• NP-складна задача
• NP-повна задача