Recently, Pasarkar et al. (2023) have introduced the new \({{\,\mathrm{\texttt{TFNP}}\,}}\) subclass called \({{\,\mathrm{\texttt{PLC}}\,}}\) that contains the class \({{\,\mathrm{\texttt{PPP}}\,}}\) ; they also have proven that several search problems related to extremal combinatorial principles (e.g., Ramsey’s theorem and the sunflower lemma) belong to \({{\,\mathrm{\texttt{PLC}}\,}}\) . This paper discusses the complexity of the three generalizations of Constrained Long Choice, a \({{\,\mathrm{\texttt{PLC}}\,}}\) -complete problem. We first discuss the parallel variant: Given a Long Choice instance and \(\varvec{m}\) beginning elements, find \(\varvec{m}\) Constrained Long Choice solutions. We show that this variant is \({{\,\mathrm{\texttt{FP}}\,}}_{\Vert }^{{{\,\mathrm{\texttt{PLC}}\,}}}\) -complete. Next, we discuss the iterative variant: Given a Constrained Long Choice instance, a process function that specifies the next beginning element depending on the current solution, and an iteration parameter \(\varvec{T}\) , find \(\varvec{T}\) Long Choice solutions satisfying the suitable conditions. We prove that this variant is \({{\,\mathrm{\texttt{FP}}\,}}^{{{\,\mathrm{\texttt{PLC}}\,}}}\) -complete. Finally, we consider the inductive variant, which is an iterative variant with the inductive principle. We prove that the inductive variant is not only \({{\,\mathrm{\texttt{PLC}}\,}}\) -hard but also \({{\,\mathrm{\texttt{PLS}}\,}}\) -hard, where the class \({{\,\mathrm{\texttt{PLS}}\,}}\) is the set of all search problems that are solvable by a local search method. Furthermore, we show that our iterative and inductive variants are closed under the Turing reduction.
