Czy można rozpoznać w wieloskładnikowej probabilistycznej przestrzeni sublogarytmicznej?

Zastanów się nad językiem . $\mathtt{EQUALITY} = \{ a^nb^n \mid n \geq 0 \}$

Wiadomo, że nie może zostać rozpoznany przez żadną maszynę Turinga (ATM) na przemian z przestrzenią sublogarytmiczną (Szepietowski, 1994) . (Istnieje bankomat wykorzystujący przestrzeń sublogarytmiczną dla członków, ale nie dla wszystkich osób niebędących członkami!) $\mathtt{EQUALITY}$

Z drugiej strony Freivalds (1981) wykazał, że probabilistyczne maszyny Turinga (PTM) z ograniczonym błędem o stałej przestrzeni mogą rozpoznawać ale tylko w wykładniczym oczekiwanym czasie ( Greenberg i Weiss, 1986 ). Później wykazano, że żaden błąd ograniczający -space PTM nie może rozpoznać nieregularnego języka w wielomianowym oczekiwanym czasie ( Dwork and Stockmeyer, 1990 ). Moje pytanie brzmi $\mathtt{EQUALITY}$ $o(\log\log n)$

czy wielogodzinne PTM w przestrzeni sublogarytmicznej rozpoznają z błędem ograniczonym. $\mathtt{EQUALITY}$

space-bounded polynomial-time

— Abuzer Yakaryilmaz
źródło

Nie rozumiem, dlaczego zredagowano tytuł pytania, aby usunąć z niego definicję języka. Nikt nie wyobraża sobie, że „sprawdzanie równości” oznacza „decyduj o języku .

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

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

— David Richerby

@DavidRicherby: Dziękujemy za sugestie dotyczące edytowania i komentarze. Po prostu wolę mniej technicznych tytułów. W przeciwnym razie powinienem dodać nie tylko definicję języka, ale także terminy „rozpoznany”, „błąd ograniczający” i „probabilistyczne maszyny Turinga”.

— Abuzer Yakaryilmaz

Tytuł powinien powiedzieć ludziom, o co chodzi w tym pytaniu. Jest to społeczność badaczy TCS i każdy badacz TCS wie, co znaczy „rozpoznany”, „ograniczony błąd” i „probabilistyczna maszyna Turinga”. Podobnie, „ ” jest natychmiast zrozumiałe dla badaczy TCS; „sprawdzanie równości” nie jest. Gdyby langauge miał powszechnie znaną nazwę, użycie tej nazwy byłoby w porządku, ale, o ile mi wiadomo, tak nie jest.

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

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

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

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

— David Richerby,

Czy istnieje nieregularny język jednoargumentowy, który można rozpoznać w przestrzeni (na deterministycznej bazie TM)? Jeśli nie, ten sam dowód może tu działać.

o (\log n)

$o(\log n)$

— domotorp

@domotorp: Tak, istnieją nieregularne języki rozpoznawane przez -space deterministyczne TM. (Patrz (Szepietowski, 1994) podany powyżej.)

\log \log n

$\log\log n$

— Abuzer Yakaryilmaz

Znalazłem odpowiedź na moje własne pytanie. Wynik został podany w rozdziale 5 Karpińskiego i Verbeek, 1987 .

Dla dowolnego wejścia o długości PTM może z dużym prawdopodobieństwem zbudować przestrzeń (Rozdział 4). (Z bardzo małym prawdopodobieństwem, urządzenie może również konstruować przestrzeni logarytmicznej, a to może być postrzegane jako „zwrotu” algorytmu). Następnie PTM może zdecydować, czy numery „s ( ), a ” s ( ) są równe z dużym prawdopodobieństwem przy użyciu przestrzeni w czasie wielomianowym. $n$ $\Theta(\log \log n)$ $a$ $n$ $b$ $m$ $O(\log \log n)$

Pomysł jest następujący. Jeśli , to tak, że ( Alt and Mehlron, 1976 ). PTM może wybrać losowe za pomocą spacji . jest wystarczająca, aby zachować licznik i tak stara ponad połowę wszystkich możliwych „ów. Przypadek można wykryć z prawdopodobieństwem większym niż . $n \neq m$ $\exists k \leq 4 \log(n+m)$ $n \not\equiv m \mod k$ $k$ $O(\log \log n)$ $O(\log \log n)$ $k$ $n \neq m$ $1 \over 2$

— Abuzer Yakaryilmaz
źródło