Sparse Sets in NP-P: EXPTIME versus NEXPTIME

Juris Hartmanis Vivian Sewelson Neil Immerman

Published in: STOC (1983)

Keyphrases

upper bound
np complete
pspace complete
description logics
satisfiability problem
high dimensional
np hard
neural network
sparse data
datalog programs
compressed sensing
tree automata
special case
computational complexity
optimal solution
sparse representation
database systems