Relativizing complexity classes with sparse oracles.

Timothy J. Long Alan L. Selman

Published in: J. ACM (1986)

Keyphrases

tractable cases
test cases
decision problems
complexity measures
random projections
database
sparse data
data sets
real world
sparse representation
intrinsic complexity