Ruzzo-Simon-Tompa Orakel-Zugangsmechanismus

$\mathsf{NL} \nsubseteq \mathsf{P}$

Betrachten Sie nun Schaltungsfamilien mit Orakeltoren - beispielsweise $A^B$ , wobei $A$ eine Schaltungskomplexitätsklasse ist, die einen Lograum mit Orakelzugriff auf eine andere Klasse $B$ über an die Basis von A angehängte Orakeltore enthält $A$. Gibt es pathologische Beispiele, die dem für solche Klassen bekannten Ladner-Lynch-Papier ähneln? Was wäre eine RST-ähnliche Einschränkung für solche Klassen? Wenn es tatsächlich solche Beispiele gibt, kann ich zu Recht davon ausgehen, dass ein RST-Analogon darauf bestehen würde, dass $A$ eine logspace-einheitliche Schaltungsfamilie ist?

Eine Definition des Orakelzugriffs, die für Komplexitätsklassen kleiner Schaltkreise (die Hierarchien $AC^k$ und $NC^k$ ) sowie für logarithmische Raumklassen mit der Eigenschaft funktioniert , dass alle bekannten Einschlüsse relativieren, finden Sie in diesem Artikel:

Klaus Aehlig, Stephen Cook und Phuong Nguyen: Relativierung kleiner Komplexitätsklassen und ihrer Theorien, CSL 2007, Springer LNCS 4646