computable in polynomial time by nonadaptively accessing an oracle in NP is effectively
included in PF NP k⌈ log n⌉—1, the class of functions that are computable in polynomial k⌈
log n⌉—1 queries to an oracle in NP.¶ We draw several observations and relationships
between the following two properties of a complexity class \calC: whether there exists a
truthtable hard p-selective language for \calC, and whether polynomially-many nonadaptive …