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?
Complete problems and relativization barriers for nonuniform complexity classes
complexity theory;relativization