Конечно, вы просто должны быть осторожны, думая о том, что значит иметь оракула.
Проблема возникает из раздражающего злоупотребления обозначения мы используем в CS: В заявлении , относится к набору языков. Но в заявлении , относится к классу машин Тьюринга (determinstic полиномиальных по ТМС). Вы должны думать об этих двух с , как из совершенно разных типов.P=NPPPA=NPAPP
Таким образом, даже если два набора языков и одинаковы, детерминированные многопользовательские TM по-прежнему не работают так же, как недетерминированные. В частности, при наличии оракула недетерминированный ТМ может «задавать много вопросов одновременно», чего не может делать обычная ТМ. Таким образом, даже если они выбирают один и тот же набор языков, когда ни одному типу машины не оказывается дополнительная помощь, оракул может помочь одному типу машины больше, чем другому.PNP