Note on Constrained Long Choice with Multiple Beginning Elements

Abstract Recently, Pasarkar et al. (2023) have introduced the new $${{\,\mathrm{\texttt{TFNP}}\,}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mspace/> <mml:mi>TFNP</mml:mi> <mml:mspace/> </mml:mrow> </mml:math> subclass called $${{\,\mathrm{\texttt{PLC}}\,}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mspace/> <mml:mi>PLC</mml:mi> <mml:mspace/> </mml:mrow> </mml:math> that contains the class $${{\,\mathrm{\texttt{PPP}}\,}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mspace/> <mml:mi>PPP</mml:mi> <mml:mspace/> </mml:mrow> </mml:math> ; 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}}\,}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mspace/> <mml:mi>PLC</mml:mi> <mml:mspace/> </mml:mrow> </mml:math> . This paper discusses the complexity of the three generalizations of Constrained Long Choice , a $${{\,\mathrm{\texttt{PLC}}\,}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mspace/> <mml:mi>PLC</mml:mi> <mml:mspace/> </mml:mrow> </mml:math> -complete problem. We first discuss the parallel variant: Given a Long Choice instance and $$\varvec{m}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> </mml:mrow> </mml:math> beginning elements, find $$\varvec{m}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>m</mml:mi> </mml:mrow> </mml:math> Constrained Long Choice solutions. We show that this variant is $${{\,\mathrm{\texttt{FP}}\,}}_{\Vert }^{{{\,\mathrm{\texttt{PLC}}\,}}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mrow> <mml:mspace/> <mml:mi>FP</mml:mi> <mml:mspace/> </mml:mrow> <mml:mrow> <mml:mo>‖</mml:mo> </mml:mrow> <mml:mrow> <mml:mspace/> <mml:mi>PLC</mml:mi> <mml:mspace/> </mml:mrow> </mml:msubsup> </mml:math> -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}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow> </mml:math> , find $$\varvec{T}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>T</mml:mi> </mml:mrow> </mml:math> Long Choice solutions satisfying the suitable conditions. We prove that this variant is $${{\,\mathrm{\texttt{FP}}\,}}^{{{\,\mathrm{\texttt{PLC}}\,}}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mrow> <mml:mrow> <mml:mspace/> <mml:mi>FP</mml:mi> <mml:mspace/> </mml:mrow> </mml:mrow> <mml:mrow> <mml:mspace/> <mml:mi>PLC</mml:mi> <mml:mspace/> </mml:mrow> </mml:msup> </mml:math> -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}}\,}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mspace/> <mml:mi>PLC</mml:mi> <mml:mspace/> </mml:mrow> </mml:math> -hard but also $${{\,\mathrm{\texttt{PLS}}\,}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mspace/> <mml:mi>PLS</mml:mi> <mml:mspace/> </mml:mrow> </mml:math> -hard, where the class $${{\,\mathrm{\texttt{PLS}}\,}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mspace/> <mml:mi>PLS</mml:mi> <mml:mspace/> </mml:mrow> </mml:math> 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.