Mechanizm dostępu do wyroczni Ruzzo-Simon-Tompa

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.$\mathsf{NL} \nsubseteq \mathsf{P}$

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 $A^B$$A$$B$$A$$A$

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 $AC^k$$NC^k$

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