Kann

Betrachten Sie die Sprache . $\mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \}$

Es ist bekannt, dass von keiner sublogarithmisch-raumwechselnden Turing-Maschine (ATM) erkannt werden kann (Szepietowski, 1994) . (Es gibt einen Geldautomaten, der sublogarithmischen Raum für Mitglieder, aber nicht für alle Nichtmitglieder verwendet!) $\mathtt{EQUALITY}$

Andererseits zeigte Freivalds (1981) , dass Turing-Maschinen (PTMs) mit beschränktem Fehler und konstantem Raum probabilistisch jedoch nur in exponentiell erwarteter Zeit ( Greenberg und Weiss, 1986 ). Später wurde gezeigt, dass kein PTM mit beschränktem Fehler eine nicht reguläre Sprache in der erwarteten polynomiellen Zeit erkennen kann ( Dwork und Stockmeyer, 1990 ). Meine Frage ist $\mathtt{EQUALITY}$ $o(\log\log n)$

ob PTMs mit Poly-Time-Sublogarithmic-Space mit -Error erkennen. $\mathtt{EQUALITY}$

space-bounded polynomial-time Abuzer Yakaryilmaz
quelle

Ich verstehe nicht, warum der Fragentitel bearbeitet wurde, um die Definition der Sprache daraus zu entfernen. Niemand wird , dass „tun Gleichheitsprüfung“ bedeutet , sich vorzustellen , „entscheiden die Sprache

{a^{n} b^{n} ∣ n \geq 0}

$\{a^nb^n\mid n\geq 0\}$ .

David Richerby

@DavidRicherby: Danke für deinen Bearbeitungsvorschlag und Kommentar. Ich bevorzuge einfach weniger technische Titel. Ansonsten sollte ich nicht nur die Definition der Sprache, sondern auch die Ausdrücke "erkannt", "begrenzter Fehler" und "probabilistische Turing-Maschinen" hinzufügen.

Abuzer Yakaryilmaz

Der Titel sollte den Leuten sagen, worum es bei der Frage geht. Dies ist eine Gemeinschaft von TCS-Forschern, und jeder TCS-Forscher weiß, was "erkannte", "begrenzte Fehler" und "probabilistische Turing-Maschine" bedeuten. Ebenso ist "

{a^{n} b^{n} ∣ n \geq 0}

$\{a^nb^n\mid n\geq 0\}$ " für TCS-Forscher sofort verständlich. "Gleichheitsprüfung durchführen" ist nicht. Wenn die Sprache

{a^{n} b^{n} ∣ n \geq 0}

$\{a^nb^n\mid n\geq 0\}$ einen allgemein verstandenen Namen hätte, wäre es in Ordnung, diesen Namen zu verwenden, aber soweit ich weiß, ist dies nicht der Fall.

David Richerby

Gibt es eine nicht reguläre unäre Sprache, die im

-Raum (auf einem deterministischen TM) erkannt werden kann ? Wenn nicht, könnte der gleiche Beweis hier funktionieren.

o (\log n)

$o(\log n)$

Domotorp

@domotorp: Ja, es gibt nicht reguläre Sprachen, die von

-space deterministischen TMs erkannt werden. (Siehe (Szepietowski, 1994) oben angegeben.)

\log \log n

$\log\log n$

Abuzer Yakaryilmaz

Ich habe eine Antwort auf meine eigene Frage gefunden. Das Ergebnis wurde in Abschnitt 5 von Karpinski und Verbeek, 1987 angegeben .

Für jede Eingabe der Länge kann ein PTM mit hoher Wahrscheinlichkeit einen -Raum aufbauen (Abschnitt 4). (Mit einer sehr geringen Wahrscheinlichkeit kann die Maschine auch einen logarithmischen Raum aufbauen, und dies kann als "Nachteil" des Algorithmus angesehen werden.) Dann kann der PTM entscheiden, ob die Zahlen von ( ) und ( ) sind ( ) sind mit hoher Wahrscheinlichkeit gleich, indem der Raum in der Polynomzeit verwendet wird. $n$ $\Theta(\log \log n)$ $a$ $n$ $b$ $m$ $O(\log \log n)$

Die Idee ist wie folgt. Wenn , dann derart , dass $n \neq m$ $\exists k \leq 4 \log(n+m)$ (Alt und Mehlron, 1976). Der PTM kann ein zufälliges auswählen,indemer den Speicherplatzverwendet. reicht auch aus, um einen Zähler zu führen und so mehr als die Hälfte aller möglichenversuchen. Der Fall vonkann mit einer Wahrscheinlichkeit von mehr alserkannt werden. $n \not\equiv m \mod k$ $k$ $O(\log \log n)$ $O(\log \log n)$ $k$ $n \neq m$ $1 \over 2$

Abuzer Yakaryilmaz
quelle

Kann

Antworten: