Wykazać, że funkcja boolowska obliczalna w T (n) przez maszynę RAM jest w DTIME (T (n) ^ 2)

10

Pytanie brzmi: ćwiczenie 1.9 z książki Arory-Barak Computational Complexity - A Modern Approach :

Zdefiniuj maszynę RAM Turing jako maszynę Turinga, która ma pamięć o dostępie swobodnym. Sformalizujemy to w następujący sposób: Maszyna ma nieskończoną tablicę A, która jest inicjalizowana dla wszystkich spacji. Uzyskuje dostęp do tej tablicy w następujący sposób. Jedna z taśm roboczych urządzenia jest oznaczona jako taśma adresowa. Również maszyna ma dwa specjalne symbole alfabetu oznaczone przez R i W oraz dodatkowy stan oznaczony przez q_access. Ilekroć maszyna wprowadza q_access, jeśli jej taśma adresowa zawiera „i'R (gdzie„ i ”oznacza binarną reprezentację i), wówczas wartość A [i] jest zapisywana w komórce obok symbolu R. Jeśli taśma zawiera „i'Wa (gdzie a to jakiś symbol w alfabecie maszyny), wówczas A [i] jest ustawiane na wartość a.

Pokaż, że jeśli funkcja boolowska jest obliczalna w czasie T (n) (przez pewien czas T konstruowalny w czasie ) przez pamięć RAM TM, to jest w \ mathrm {DTIME} (T (n) ^ 2) .fT D T I M E ( T ( n ) 2 )T(n)TDTIME(T(n)2)

Trywialne rozwiązanie polegające na użyciu dodatkowych par zapisu taśmy (adres, wartość) okazuje się w DTIME(T(n)3) , ponieważ taśma może mieć rozmiar O(T(n)2) z parami O(T(n)) podczas gdy adres każdej pary może mieć rozmiar O(T(n)) .

complexity-theory turing-machines machine-models simulation cc
źródło
Skąd znasz rozmiar adresu związany? Czy mój pierwszy zapis nie może być ? A jeśli możesz powiązać go z , to rozmiar adresu to , a nie . 22T(n)T(n)log⁡(T(n))T(n)
Xodarap,
1
Ponieważ adres powinien być zapisany na taśmie przez maszynę Turinga w czasie , rozmiar (tj. Długość łańcucha) adresu nie może przekraczać , dostępna przestrzeń adresowa to . T(n)O(T(n))O(2T(n))
cc
3
Zauważ, że Arora i Barak wyraźnie proszą we wstępie o inne, niepublikowane odpowiedzi na swoje pytania. Zobacz także zasady dotyczące pytań domowych .
Kaveh
Przepraszam za to. Po prostu studiuję książkę i mam kłopoty z tym pytaniem. Nie wiem, czy taka symulacja naprawdę istnieje, czy to tylko literówka. Jeśli znasz odpowiedź, wyślij mi e-maila na adres [email protected], a następnie zamknę pytanie. O(T(n)2)
cc
Więcej informacji znajdziesz w pierwszym rozdziale podręcznika informatyki teoretycznej.
Kaveh

Odpowiedzi:

2

W komentarzach piszesz :

Ponieważ adres powinien być zapisany na taśmie przez maszynę Turinga w czasie , rozmiar (tj. Długość łańcucha) adresu nie może przekraczać .O ( T ( n ) )T(n)O(T(n))

Czy możesz użyć podobnego argumentu, aby poprawić granice

[Taśma] może mieć rozmiar z parami podczas gdy adres każdej pary może mieć rozmiar .O ( T ( n ) ) O ( T ( n ) )O(T(n)2)O(T(n))O(T(n))

wspomniałeś w pytaniu? Być może będziesz musiał pamiętać, jakie operacje są możliwe w stałym czasie na pamięci RAM, czyli przy użyciu dokładnej definicji używanej przez autorów.

Raphael
źródło
Mam nadzieję, że ta podpowiedź jest na tyle niejasna, by uszanować życzenia autorów książki, ale również nieco pomocna. (Heurystyka: Powiedziałbym studentowi tyle samo, jeśli problem został podany jako ćwiczenie. Prawdopodobnie jednak nie na egzaminie.)
Raphael