P (сложность)

• Определение и свойства класса P

  • P — это класс задач, которые могут быть решены за полиномиальное время. 
  • Задачи в P могут быть решены с использованием детерминированных алгоритмов. 
  • P включает в себя задачи, которые могут быть решены за полиномиальное время на всех входных данных. 

• Примеры задач в P

  • Задачи линейного программирования и поиска максимального соответствия являются примерами задач в P. 
  • Задача определения простоты числа также находится в P. 

• Отношения с другими классами сложности

  • P является подмножеством NP, но это не доказано. 
  • L строго содержится в PSPACE, но неизвестно, равно ли оно P. 
  • P/poly — это класс задач, которые могут быть решены за детерминированное полиномиальное время с помощью рекомендаций. 

• Свойства и история класса P

  • Алгоритмы с полиномиальным временем работы замкнуты по составу. 
  • P считается машинно-независимым классом. 
  • P может быть описано в логике первого порядка с добавлением оператора наименьшей фиксированной точки. 
  • Кобэм и Эдмондс считаются изобретателями понятия полиномиального времени. 

• Рекомендации по литературе

  • Для более подробного изучения класса P рекомендуется обратиться к книге «Введение в алгоритмы» Кормена и др.