DIMACS TR: 93-31

Constructing Language Instances Based on Partial Information

Author: Laura A. Sanchis


We investigate the problem of when it is possible to efficiently construct an instance of a given language in P or NP, based on partial information provided about the desired instance. We model this problem by specifying a prefix and a length for the string to be produced. Our results suggest that it may be harder to find efficient constructors for languages in NP if more information is provided about the desired element (assuming that P is not equal to NP). Specifically, for large enough prefix functions, polynomial-time prefix-based constructors cannot exist for all languages in NP unless P=NP. For smaller prefix functions, the existence of such constructors cannot be determined using techniques that relativize, under the assumption that $\mbox{P} \neq \mbox{NP}$. We also show through relativizations and other results, what appears to be a pattern of increasing difficulty for efficient construction as the prefix function increases within this range. For languages in P, however, the difficulty of construction first increases and then appears to decrease as the size of the prefix is increased. We also relate prefix-based construction to that based on more general parameter functions for the strings. In addition, we examine the related ranking problem in the same context, and prove some results about the existence of prefix-based rankers for languages in P and NP.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-31.ps
DIMACS Home Page