DIMACS TR: 93-31
Constructing Language Instances Based on Partial Information
Author: Laura A. Sanchis
ABSTRACT
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