Efficient Language Instance Generation

For many familiar languages in P or NP, such as the set of connected graphs or the set of satisfiable CNF boolean formulas, it appears easy to determine whether there exist any instances in the language having a certain size, and even to construct an instance of the desired size on demand. With a little more thought one can also come up with polynomial time nondeterministic or probabilistic procedures which can output all instances of the language of a given size, albeit with repetitions and not necessarily in a uniform manner. In this paper we investigate whether such efficient procedures exist for all languages in P or NP. We exhibit relativizations which show that this question cannot be easily answered. We also relate construction, generation, and categorical generation (generation with unique computation path for each string generated, i.e. no repetitions), to the existence of sparse languages in NP-P and in Dp-P. We give a characterization of the languages in NP which can be efficiently constructed from which it can be deduced that all languages in NP can be efficiently constructed if and only if all languages in P can be efficiently constructed. We also deal with parameter-based generation, with construction in the polynomial time hierarchy, and with the existence of certain types of generators viewed as NP machines