Some Graph Problems with Equivalent Lower Bounds for Query Complexity.

Rusins Freivalds Renate Praude Lelde Lace

Published in: FCS (2005)

Keyphrases

lower bound
query complexity
objective function
upper bound
concept class
min sum
databases
np hard
vc dimension
membership queries
machine learning
np complete
learning theory
equivalence queries