Do nonuniform complexity classes like NP/poly have complete problems?

Are there relativization barriers for separations of nonuniform complexity classes?

One way to interpret the second question is by asking whether there are computable languages A and B with (P/poly)^A = (NP/poly)^A and (P/poly)^B != (NP/poly)^B). Assuming the answer to both questions is "no", one reason might be that "computable" has to be replaced by "computable/poly" (whatever that might mean) and that "polytime reductions" for complete problems have to be replaced by "polytime/poly reductions" (whatever that might mean).

Is the answer to the first two questions "no", if we insist on "polytime reductions" and "computable (oracle) languages"? Are there reasonable notions of "polytime/poly reductions" and "computable/poly" languages for which the answers become "yes"?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.