On graph-theoretic lemmata and complexity classes

Several new complexity classes of search problems that lie between the classes FP and FNP are defined. These classes are contained in the class TFNP of search problems that always have a solution. A problem in each of these new classes is defined in terms of an implicitly given, exponentially large graph, very much like PLS (polynomial local search). The existence of the solution sought is established by means of a simple graph-theoretic lemma with an inefficiently constructive proof. Several class containments and collapses, resulting in the two new classes PDLF⊆PLF are shown; the relation of either class of PLS is open. PLF contains several important problems for which no polynomial-time algorithm is presently known