69000

Klasy złożoności I

Klasa zloz 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:

TIME( f (n)) - oaiacza zbiór j, ezykówL akceptowalnych przez determistyczna, maszynę, Turinga M o zloz onos ci czasowej f (n),

SPACE( f (n)) - oznacza zbiór j, ezykówL akceptowalnych przez determistyc zna, maszynę, Turinga M o zlozonoscipamie, ciowejf (n), NTIME( f (n)) - oznacza zbiór j, ezykówL akceptowalnych przez niedetermistyczna, maszynę, Turinga M o zloz onos ci czasowej f (n), NSPACE( f (n)) - oznacza zbiór j, ezykówL akceptowalnych przez niedetermistyczna, maszynę, Turinga M o zloz onos cipamie, ciowejf (n).