ON UNIVERSALLY POLYNOMIAL CONTEXT-FREE LANGUAGES
Nicholas Trân · International Journal of Foundations of Computer Science · 2002
A language is universally polynomial if its intersection with every NP-complete language is in P. Such a language would provide an automatic method for generating easy instances of intractable problems. In this note, we give a complete characterization of universally polynomial languages that are context-free, answering an open question in [4].