Emulacja Oblivious Turing Machine w dolnej granicy

Czy istnieje dowód, że emulacji maszyny Turinga na nieświadomej maszynie Turinga nie można wykonać w mniej niż gdzie jest liczbą kroków, które wykonuje maszyna Turinga ? Czy to tylko górna granica? $\mathcal{O}\left(m\log m\right)$ $m$

W artykule Paula Vitányi o relatywizowanych, nieświadomych maszynach Turinga, twierdzi Vitányi

„Oni [ Pippenger i Fischer, 1979 ] wykazali, że tego wyniku nie można ogólnie poprawić, ponieważ istnieje język L, który jest rozpoznawany przez 1-taśmową maszynę Turinga czasie rzeczywistym , i każdą nieświadomą maszynę Turinga rozpoznającą musi użyj co najmniej kroku kroków ". $M$ $M'$ $L$ $O(n \log n)$

Powinno to oznaczać jako bezwzględną granicę. Nie znalazłem jednak na to żadnego dowodu $O(m \log m)$

Pippenger, Nicholas; Fischer, Michael J. , Relacje między miarami złożoności , J. Assoc. Comput. Mach. 26, 361–381 (1979). ZBL0405.68041 .

Jakieś pomysły? Ponadto, jaka jest złożoność przestrzenna tej emulacji? O ile wiem, konwersja na uniwersalną maszynę Turinga podwaja tylko długość taśmy. Czy mogę założyć, że złożoność przestrzeni to przy złożoności przestrzeni oryginalnej maszyny Turinga? $\mathcal{O}\left(l\right)$ $l$

cc.complexity-theory turing-machines Willem Van Onsem
źródło

Dopasuj nawiasy i określ, co to jest T. Myślę, że wciąż jest otwarty, ale nie jestem ekspertem.

Tsuyoshi Ito,

czym jest nieświadoma maszyna Turinga?

Suresh Venkat

Oblivious Turing Machine to maszyna Turinga, w której ruch głowic zależy tylko od długości wejścia, a nie od samego wejścia. Na przykład wyszukiwanie liniowe (jeśli głowa porusza się, dopóki nie osiągnie końca wejścia)

Willem Van Onsem

Odpowiedzi:

Jak wspomniano powyżej, ogólnie nie wiadomo, czy istnieje szybsza nieświadoma symulacja.

Ale ciekawe dolne granice tego problemu są znane w bardziej ograniczonych warunkach. Na przykład, co jeśli chcesz niepomny symulacja który zachowuje nie tylko czas , ale także wykorzystanie miejsca ? Beame i Machmouchi udowodnili ostatnio, że interesujący kompromis czasoprzestrzenny jest niższy dla tego problemu: albo przestrzeń musi wzrosnąć o współczynnik , albo czas musi wzrosnąć o współczynnik . $t$ $s$ $n^{1-o(1)}$ $\Omega(\log n \cdot \log \log n)$

Artykuł jest tutaj: http://eccc.hpi-web.de/report/2010/104/

Ryan Williams
źródło

Tylko rozszerzony komentarz: Myślę, że wciąż jest to otwarty problem; zajrzyj na blog Liptona i Regana, aby znaleźć ciekawe dyskusje na temat poprawy wyników twierdzenia Fischera-Pippengera .

Na przykład zobacz posty: Oblivious Turing Machines and a „Crock” or Circuits Bounds for Turing Machine Computations (oba datowane na 2009 rok).

W drugim poście pokazują, że lepsze ograniczenie obwodu ( ) jest możliwe przy użyciu funkcji częściowej wartości logicznej która jest przybliżona oryginalna funkcja na wejściach . $O(n \log {\log n})$ $g:2^n \to \{0,1,*\}$ $f$ $2^{n-o(n)}$

Marzio De Biasi
źródło

Przeczytałem twierdzenie Fischera-Pippengera i jest to dowód. Jednak nigdy w dowodzie nie ma elementu, który mówi, że nie ma szybszej metody. Zastanawiałem się, czy istnieje dowód, że jest to gwarantowane minimum. Jeśli spojrzysz na dowód, emulują one TM na UTM, a następnie wykonują mały hack, aby to nieświadomie. Można jednak argumentować, że pierwszy krok jest niezbędny, aby wiedzieć, jak zachowa się maszyna.

Willem Van Onsem

@CommuSoft Nikt nie sugeruje, że dowód jest niczym innym, jak dowodem z górnej granicy. Wpisy na blogu sugerują, że ulepszanie Fischera-Pippengera to otwarty problem.

Sasho Nikolov

@CommuSoft: Jest to otwarty problem ... być może istnieje szybsza metoda lub ktoś udowodni, że jest to najlepsza możliwa do osiągnięcia.

Marzio De Biasi

Cóż, czytam artykuł opublikowany przez Paula Vitányi zatytułowany „Relatywistyczna nieświadomość”, który wydaje się twierdzić, że czas wynosi co najmniej O (m log m). Jednak nie jestem jeszcze pewien, czy użyje twierdzenia Fischera-Pippengera, aby to udowodnić.

Willem Van Onsem,