Class Description

PQUERY: PSPACE With Polynomial Queries

The class of decision problems solvable in polynomial space using at most a polynomial number of queries to the oracle.

Thus, PQUERY = PSPACE, but PQUERY^A does not equal PSPACE^A for some oracles A.

Defined in [Kur83], where it was actually put forward as a serious argument (!!) against believing relativization results.

Linked From

No class.