Czym jest Czas wielomianowy (Polynomial time)?
Czas wielomianowy opisuje taki wzrost zapotrzebowania na kroki obliczeniowe, który da się ująć jako wielomian o zmiennej reprezentującej rozmiar danych wejściowych. Jeżeli algorytm potrzebuje na przykład n2 lub n3 operacji, mówimy, że działa w czasie wielomianowym. W kontekście uczenia maszynowego i ogólnie sztucznej inteligencji ta właściwość bywa kluczowym kryterium oceny, czy daną metodę da się uruchomić na realnych zbiorach danych bez nadmiernych kosztów sprzętowych lub energetycznych.
Kontekst historyczny i formalna definicja
Pojęcie czasu wielomianowego zostało spopularyzowane w latach 70. XX w. głównie przez pracę Time Hierarchy Theorem Stephena Cooka oraz niezależne analizy Richarda Karpa. Instytucjonalnie problematykę tę rozwijały Uniwersytet w Toronto, Stanford czy MIT. Formalnie mówimy, że algorytm A działa w czasie O(nk), jeśli istnieje stała k oraz stała c taka, że dla wszystkich n większych od pewnej granicy czas wykonania T(n) ≤ c·nk. W skrócie zapisujemy klasę takich problemów jako PTIME lub P.
Jak dokładnie działa Czas wielomianowy (Polynomial time)
Analiza rozpoczyna się od określenia jednostki pracy maszyny Turinga bądź modelu RAM. Następnie zlicza się maksimum nieprzystających operacji dla wejścia o wielkości n. Jeżeli sumaryczny rachunek sprowadza się do wielomianu, algorytm kwalifikuje się do PTIME. Klasyczny algorytm sortowania przez scalanie zużywa O(n log n) kroków, co, choć logarytmiczne, jest jednocześnie ograniczone przez dowolny wielomian stopnia większego od jedności, a więc mieści się w PTIME. Dla kontrastu metoda pełnego przeglądu rozwiązań problemu komiwojażera rośnie w przybliżeniu jak O(n!), co wykracza poza tę klasę.
Zastosowania w praktyce
Uczenie liniowej regresji metodą najmniejszych kwadratów, trenowanie maszyn wektorów nośnych przy pomocy wymiernie działających rozkładów macierzowych czy odwzorowanie grafów neuronowych na sprzęt GPU – wszystkie te czynności opierają się na procedurach, których złożoność można ograniczyć wielomianowo względem liczby przykładów i cech. Dzięki temu możliwe jest skalowanie eksperymentów do milionów parametrów bez gwałtownego skoku czasu treningu.
Zalety i ograniczenia
Najważniejszą zaletą jest przewidywalność wzrostu kosztów: podwojenie rozmiaru danych nie powoduje eksplozji wymagań, jak dzieje się w przypadku algorytmów wykładniczych. Z drugiej strony ocena PTIME bywa myląca, gdy wielomian ma wysoki stopień lub duży współczynnik wiodący. Algorytm o złożoności O(n10) okazuje się niepraktyczny mimo formalnej przynależności do P.
Na co uważać?
Projektując systemy AI, warto zwrócić uwagę na implementacyjne stałe ukryte w notacji O. Równie istotna jest pamięciochłonność, która w skrajnych przypadkach potrafi zniweczyć korzyści z czasu wielomianowego. Należy też pamiętać, że niektóre zadania, jak dokładne wnioskowanie w sieciach Bayesa o wysokiej łączności, pozostają co do zasady problemami #P-trudnymi, toteż wymagają przybliżeń lub heurystyk, mimo że ich uproszczone wersje mieszczą się w PTIME.
Dodatkowe źródła
Rozszerzone omówienie klasy P można znaleźć na stronie Wikipedia – Klasa P. Historyczne tło zagadnienia przedstawia artykuł Stephena Cooka dostępny w cyfrowym archiwum ACM Digital Library. Aktualne badania nad praktycznymi granicami czasu wielomianowego w uczeniu głębokim omawia praca „On the Computational Complexity of Training Neural Networks” na arXiv.
