Полиномијално време

У теорији комплексности, полиномијално време се односи на време израчунавања проблема, где време, -{m(n)}-, није веће од полиномијалне функције величине проблема, -{n}-. Математички записано у нотацији великог О, ово значи $m(n)=O(n^k)$ где је -{k}- нека константа која може зависити од проблема. На пример, алгоритам за сортирање квиксорт за -{n}- бројева захтева највише $n^2$ операција. Стога му је потребно време $O(n^2)$, па се ради о алгоритму полиномијалног времена.

Математичари некада користе појам полиномијалног времена у односу на дужину улаза као дефиницију брзог рачунања, као супротност супер-полиномијалном времену, које се односи на све шта је спорије од тога. Експоненцијално време је пример супер-полиномијалног времена.

Класа комплексности проблема одлучивања који могу бити решени детерминистичком Тјуринговом машином у полиномијалном времену је позната као класа П. Класа проблема одлучивања чије се потенцијално решење може проверити у полиномијалном времену је се назива класом НП. Еквивалентно, НП је класа проблема одлучивања који се могу решити у полиномијалном времену недетерминистичком Тјуринговом машином (НП значи Недетерминистичко Полиномијално време).

Подкласе полиномијалног времена

• Константно време: -{O(1)}-
• Линеарно време: -{O(n)}-
• Квадратно време: -{O(n²)}-
• Кубно време: -{O(n³)}-

Алгоритми којима је потребно линеарно, логаритамско и константно време су бржи подскуп алгоритама који захтевају полиномијално време.

Види још

• Константно време
• Линеарно време
• Експоненцијално време
• Теорија комплексности
• Класе комплексности П и НП
• НП
• Алгоритам
• Велико О