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

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 (przez pewien czas konstruowalny w czasie ) przez pamięć RAM TM, to jest w . $f$ $T(n)$ $T$ $\mathrm{DTIME}(T(n)^2)$

Trywialne rozwiązanie polegające na użyciu dodatkowych par zapisu taśmy (adres, wartość) okazuje się w $\mathrm{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))$ .

— 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 .

2^{2^{T (n)}}

$2^{2^{T(n)}}$

T (n)

$T(n)$

\log (T (n))

$\log\left(T(n)\right)$

T (n)

$T(n)$

— Xodarap,

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)

$T(n)$

O (T (n))

$O(T(n))$

O (2^{T (n)})

$O(2^{T(n)})$

— cc

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 ccqmpux@gmail.com, a następnie zamknę pytanie.

O (T (n)^{2})

$O(T(n)^2)$

— cc

Więcej informacji znajdziesz w pierwszym rozdziale podręcznika informatyki teoretycznej.

— Kaveh

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ć . $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)^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