Клас складності 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]

Приклади[ред.ред. код]

Посилання[ред.ред. код]

  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. 

Дивіться також[ред.ред. код]