We examined the effect of goal specificity on a search in two problem spaces: a hypothesis space and an instance space. Two hypotheses were considered: 1) a nonspecific goal facilitates a search in a hypothesis space more than a specific goal, and 2) as a hypothesis space is searched more, the performance in discovering the target rule improves. We also defined an initial hypothesis space consisting of initially considered hypotheses, and investigated the effect of this initial hypothesis space on the goal specificity effect. The results of three experiments indicated that when an initial hypothesis space was offered, the goal specificity effect was observed. A nonspecific goal actually facilitated a search in the hypothesis space. When, however, no initial hypothesis space was offered, the goal specificity effect was not confirmed. We also found that the facilitation of the hypothesis space search improved performance in discovering the target rule.