Mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa

11

W artykule na temat relatywizacji obliczeń przestrzeni logicznej Ladner i Lynch konstruują wyrocznię, do której . W literaturze można znaleźć więcej patologicznych przykładów. Czytałem kilka artykułów na temat relatywizowanych małych klas kosmicznych, a jednym z podstawowych narzędzi w tym obszarze jest mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa (RST), który wymaga deterministycznej, niedeterministycznej maszyny Turinga działającej w przestrzeni zapytania do wyroczni.NLP

Rozważmy teraz rodzinom obwodów z Oracle Gates - powiedzmy, , gdzie jest klasa złożoności obwód zawierający logspace Oracle dostępu do innej klasy , za pomocą dołączonych do bram oracle podstawie . Czy są jakieś patologiczne przykłady podobne duchowo do pracy Ladnera-Lyncha, znanej z takich klas? Jakie byłoby ograniczenie podobne do RST dla takich klas? W przypadku, gdy rzeczywiście istnieją takie przykłady, mam rację, zgadując, że analog RST nalegałby, aby był rodziną obwodów jednolitych w przestrzeni logicznej? A B A AABABAA

Nikhil
źródło

Odpowiedzi:

8

Definicja dostępu do Oracle, która działa dla klas złożoności małych obwodów ( hierarchie i ), a także dla klas przestrzeni logarytmicznej, z właściwością relatywizującą wszystkie znane wtrącenia, można znaleźć w tym artykule: N C kACkNCk

Klaus Aehlig, Stephen Cook i Phuong Nguyen: Relatywizacja klas małych złożoności i ich teorii, CSL 2007, Springer LNCS 4646

Jan Johannsen
źródło
1
Dzięki za wskaźnik. Ale wciąż nie mam jasnego pojęcia, w jaki sposób RST stosuje się do obwodów z bramkami wyroczni. Mam nadzieję, że nie masz nic przeciwko, jeśli poczekam chwilę, aby zobaczyć, czy są jakieś inne interesujące kwestie w tej sprawie, zanim zaakceptuję twoją odpowiedź.
Nikhil