We investigate the complexity of learning for the well-studied model i
n which the learning algorithm may ask membership and equivalence quer
ies. While complexity theoretic techniques have previously been used t
o prove hardness results in various learning models, these techniques
typically are not strong enough to use when a learning algorithm may m
ake membership queries. We develop a general technique for proving har
dness results for learning with membership and equivalence queries lan
d for more general query models). We apply the technique to show that,
assuming NP not equal co-NP, no polynomial-time membership and (prope
r) equivalence query algorithms exist for exactly learning read-thrice
DNF formulas, unions of k greater than or equal to 3 halfspaces over
the Boolean domain, or some other related classes. Our hardness result
s are representation dependent, and do not preclude the existence of r
epresentation independent algorithms. The general technique introduces
the representation, problem for a class F of representations (e.g., f
ormulas), which is naturally associated with the learning problem for
F. This problem is related to the structural question of how to charac
terize functions representable by formulas in F, and is a generalizati
on of standard complexity problems such as SATISFIABILITY. While in ge
neral the representation problem is in Sigma(2)(P), we present a theor
em demonstrating that for ''reasonable'' classes F, the existence of a
polynomial-time membership and equivalence query algorithm for exactl
y learning F implies that the representation problem for F is in fact
in co-NP. The theorem is applied to prove hardness results such as the
ones mentioned above, by showing that the representation problem for
specific classes of formulas is NP-hard.