Что такое класс сложности

Что означает класс сложности ? Я знаю , что ⊕ P есть класс сложности , который содержит языки А , для которых существует многочлен времени недетерминирован машина Тьюринга M такая , что х ∈ тогда и только тогда число принимающих состояний машины М на входе х нечетно.$\oplus P^{\oplus P}$$\oplus P$$A$$M$$x \in A$$M$$x$

Но что означает ? Я просто не могу понять, что на самом деле делает :)$\oplus P^{\oplus P}$

Каковы практические последствия такого класса сложности и как можно показать, что ?$\oplus P^{\oplus P} = \oplus P$

обозначает класс ⊕ P, снабженный так называемыморакуломдля ⊕ P - мы говорим, что ему была дана возможность определить, является ли строка s членом языка L, содержащегося в классе ⊕ P в одной операции.$\oplus P^{\oplus P}$$\oplus P$$\oplus P$$s$$L$$\oplus P$

Я вижу, что другой комментатор (sdcwc) связан с доказательством (см. Эти заметки на лекции из CS 538 в Rutgers ). Класс сложности С , что является оракулом к классу B таким образом, что B C = B , как говорят, низко для класса B . В этом случае мы говорим, что ⊕ P мало для себя.$\oplus P^{\oplus P} = \oplus P$$C$$B$$B^C= B$$B$$\oplus P$