5020058908

Klasy złożoności I

Klasa złoz onos'ci obliczeniowej to zbiór je_Łzykówspełniaja_Łcychokres'lone kryterium (tzn. czas i pami_Łe'c). Podstawowe klasy zło zono'sci:

TEME( f (n)) - oznacza zbiór j_ŁezykówL akceptowalnych przez determistyczna_t maszynę,. Turinga M o złoz onos'ci czasowej f (n),

SPACE( f (n)) - oznacza zbiór j_ŁezykówL akceptowalnych przez determistyczna_Łmaszyne_Ł Turinga M o złozonos'cipamie_Łciowejf (n), NTTME( f (n)) - oznacza zbiór jŁezykówL akceptowalnych przez niedetermistyczna₍maszyne_Ł Turinga Mo zlozonos'ci czasowej f(n), NSPACE( f (n)) - oznacza zbiór j_tezykówL akceptowalnych przez niedetermistyczna_Łmaszyne_Ł Turinga Mo złozonos'cipamie_Łciowejf (n).