Złożoność obliczeniowa/Test 2: Inne modele dla złożoności
Wybierz zdania prawdziwe z poniższej listy:
maszyna RAM posiada taśmę wejściową o nieskończonym alfabecie
jeżeli maszyna RAM nie używa adresowania pośredniego, to zawsze używa skończonej liczby rejestrów
maszyna RAM nie może wielokrotnie czytać tej samej komórki taśmy wejściowej
program maszyny RAM może ulegać modyfikacjom w trakcie działania
Wybierz zdania prawdziwe z poniższej listy:
przy zastosowaniu kryterium jednostajnego czas wykonania operacji nie zależy od jej argumentów
przy zastosowaniu kryterium logarytmicznego koszt dowolnej instrukcji READ można z góry ograniczyć przez stałą zależną tylko od programu
złożoność czasowa programu przy zastosowaniu kryterium logarytmicznego nie musi być wielomianowo zależna od złożoności czasowej tego samego programu przy użyciu kryterium jednostajnego
Z poniższej listy wybierz zdania prawdziwe:
jeżeli dla zadanego problemu decyzyjnego nie istnieje wielomianowy algorytm dla maszyny RAM przy zastosowaniu kryterium jednostajnego to nie istnieje wielomianowy algorytm dla maszyny Turinga
jeżeli pewien problem decyzyjny jest rozwiązywany przez maszynę RAM w użyciem stałej ilości pamięci przy użyciu kryterium logarytmicznego, to można go rozwiązać na maszynie Turinga przy użyciu stałej liczby komórek
jeżeli pewien problem decyzyjny jest rozwiązywany przez maszynę RAM w użyciem stałej ilości pamięci przy użyciu kryterium jednostajnego, to można go rozwiązać na maszynie Turinga przy użyciu stałej liczby komórek
Z poniższej listy wybierz zdania prawdziwe:
za pomocą obwodów logicznych można zaimplementować każdą funkcję przekształcającą z
każdą maszynę Turinga można przekształcić w równoważny jej obwód logiczny
każdy obwód logiczny można przekształcić do maszyny Turinga obliczającej tą samą funkcję
istnieją problemy decyzyjne wymagające liniowej złożoności czasowej przy ich rozstrzyganiu na maszynie Turinga i wykładniczej złożoności ilościowej przy implementacji za pomocą rodziny układów logicznych
