Klasy złożoności I-opracowanie

Klasy złożoności I Klasa złoz˙onos´ci obliczeniowej to zbiór je˛zyków spełniaja˛cych okres´lone kryterium (tzn. czas i pami˛e´c). Podstawowe klasy zło˙zono´sci: TIME ( f ( n )) - oznacza zbiór j˛ezyków L akceptowalnych przez determistyczna˛maszyne˛ Turinga M o złoz˙onos´ci czasowej f ( n ) , SPACE ( f ( n )) - oznacza zbiór j˛ezyków L akceptowalnych przez determistyczna˛maszyne˛ Turinga M o złoz˙onos´ci pamie˛ciowej f ( n ) , NTIME ( f ( n )) - oznacza zbiór j˛ezyków L akceptowalnych przez niedetermistyczna˛maszyne˛ Turinga M o złoz˙onos´ci czasowej f ( n ) , NSPACE ( f ( n )) - oznacza zbiór j˛ezyków L akceptowalnych przez niedetermistyczna˛maszyne˛ Turinga M o złoz˙onos´ci pamie˛ciowej f ( n ) . ... zobacz całą notatkę