Руццо-Симон-Томпа Механизм доступа оракула

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

Теперь рассмотрят схему семьи с оракулом воротами - скажем, , где классе сложности схемы , содержащая logspace с доступом оракула к другому классу , через оракул ворот приложенного к основанию . Существуют ли какие-либо патологические примеры, похожие по духу на статью Ладнера-Линча, известную такими классами? Какое RST-подобное ограничение необходимо для таких классов? Если такие примеры действительно есть, могу ли я предположить, что аналог RST будет настаивать на том, чтобы являлось семейством логарифмических схем? A B A $A^B$$A$$B$$A$$A$

Определение доступа к оракулу, которое работает для небольших классов сложности схем ( иерархии и ), а также для классов логарифмического пространства со свойством, которое релятивизируют все известные включения, можно найти в этой статье: N C $AC^k$$NC^k$

Клаус Элиг, Стивен Кук и Фуонг Нгуен: релятивизация классов малой сложности и их теории, CSL 2007, Springer LNCS 4646