Złożoność obliczeniowa/Test 2: Inne modele dla złożoności

From Studia Informatyczne

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 \{ 0, 1 \}^m \rightarrow \{ 0, 1 \}^n

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