Klasy złożoności II-opracowanie

Klasy złożoności II Klasy złoz˙onos´ci czasowej, w których funkcje sa˛wyła˛cznie asymptotyczne: P - deterministyczny czas wielomianowy, problem decyzyjny A nale˙zy do klasy P , jes´li moz˙na podac´ jego rozwia˛zanie w czasie wielomianowym - sa˛ to problemy ”łatwe” lub inaczej ”szybko rozwia˛zywalne” NP - niedeterministyczny czas wielomianowy, problem decyzyjny A nalez˙y do klasy NP , jez˙eli jego rozwia˛zanie moz˙e byc´ zweryfikowane w czasie wielomianowym; problem jest w klasie NP , je´sli mo˙ze by´c rozwia˛zany w wielomianowym czasie na niedeterministycznej maszynie Turinga, EXP - deterministyczny czas wykładniczy, NEXP - niedeterministyczny czas wykładniczy. TIME ( f ( n )) _ NTIME ( f ( n )) ... zobacz całą notatkę