Beweisen Sie, dass eine in T (n) von einer RAM-Maschine berechenbare Boolesche Funktion in DTIME (T (n) ^ 2) ist.

Die Frage ist Übung 1.9 aus Arora-Baraks Buch Computational Complexity - A Modern Approach :

Definieren Sie eine RAM-Turing-Maschine als Turing-Maschine mit Direktzugriffsspeicher. Wir formalisieren dies wie folgt: Die Maschine hat ein unendliches Array A, das für alle Leerzeichen initialisiert wird. Es greift wie folgt auf dieses Array zu. Eines der Arbeitsbänder der Maschine wird als Adressband bezeichnet. Außerdem hat die Maschine zwei spezielle Alphabetsymbole, die mit R und W bezeichnet sind, und einen zusätzlichen Zustand, den wir mit q_access bezeichnen. Wenn die Maschine q_access eingibt und ihr Adressband 'i'R enthält (wobei' i 'die binäre Darstellung von i bezeichnet), wird der Wert A [i] in die Zelle neben dem R-Symbol geschrieben. Wenn das Band 'i'Wa' enthält (wobei a ein Symbol im Alphabet der Maschine ist), wird A [i] auf den Wert a gesetzt.

Zeigen Sie, dass, wenn eine Boolesche Funktion innerhalb der Zeit (für einige Zeit konstruierbar ) durch einen RAM TM berechenbar ist, sie sich in . $f$ $T(n)$ $T$ $\mathrm{DTIME}(T(n)^2)$

Die triviale Lösung unter Verwendung zusätzlicher Bandaufzeichnungspaare (Adresse, Wert) stellt sich als , da dieses Band mit Größe Paare, während die Adresse jedes Paares die Größe . $\mathrm{DTIME}(T(n)^3)$ $O(T(n)^2)$ $O(T(n))$ $O(T(n))$

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

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

T (n)

$T(n)$

\log (T (n))

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

T (n)

$T(n)$

T (n)

$T(n)$

O (T (n))

$O(T(n))$

O (2^{T (n)})

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

Beachten Sie, dass Arora und Barak in ihrer Einführung ausdrücklich nach anderen Antworten auf ihre Fragen fragen. Siehe auch die Richtlinie zu Hausaufgabenfragen .

Kaveh

O (T (n)^{2})

$O(T(n)^2)$

Weitere Informationen finden Sie im ersten Kapitel des Handbuchs der theoretischen Informatik.

Kaveh

Beweisen Sie, dass eine in T (n) von einer RAM-Maschine berechenbare Boolesche Funktion in DTIME (T (n) ^ 2) ist.

Antworten: