{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,9]],"date-time":"2025-04-09T04:23:07Z","timestamp":1744172587060,"version":"3.40.3"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,27]],"date-time":"2024-12-27T00:00:00Z","timestamp":1735257600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,27]],"date-time":"2024-12-27T00:00:00Z","timestamp":1735257600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"JST ACT-X","award":["JPMJAX2101"],"award-info":[{"award-number":["JPMJAX2101"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,3]]},"abstract":"Abstract<\/jats:title>\n Recently, Pasarkar et al. (2023) have introduced the new \n \n $${{\\,\\mathrm{\\texttt{TFNP}}\\,}}$$<\/jats:tex-math>\n \n \n \n TFNP<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> subclass called \n \n $${{\\,\\mathrm{\\texttt{PLC}}\\,}}$$<\/jats:tex-math>\n \n \n \n PLC<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> that contains the class \n \n $${{\\,\\mathrm{\\texttt{PPP}}\\,}}$$<\/jats:tex-math>\n \n \n \n PPP<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>; they also have proven that several search problems related to extremal combinatorial principles (e.g., Ramsey\u2019s theorem and the sunflower lemma) belong to \n \n $${{\\,\\mathrm{\\texttt{PLC}}\\,}}$$<\/jats:tex-math>\n \n \n \n PLC<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. This paper discusses the complexity of the three generalizations of Constrained Long Choice<\/jats:sc>, a \n \n $${{\\,\\mathrm{\\texttt{PLC}}\\,}}$$<\/jats:tex-math>\n \n \n \n PLC<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-complete problem. We first discuss the parallel variant: Given a Long Choice<\/jats:sc> instance and \n \n $$\\varvec{m}$$<\/jats:tex-math>\n \n \n m<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> beginning elements, find \n \n $$\\varvec{m}$$<\/jats:tex-math>\n \n \n m<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n Constrained Long Choice<\/jats:sc> solutions. We show that this variant is \n \n $${{\\,\\mathrm{\\texttt{FP}}\\,}}_{\\Vert }^{{{\\,\\mathrm{\\texttt{PLC}}\\,}}}$$<\/jats:tex-math>\n \n \n \n \n FP<\/mml:mi>\n \n <\/mml:mrow>\n \n \u2016<\/mml:mo>\n <\/mml:mrow>\n \n \n PLC<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:msubsup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-complete. Next, we discuss the iterative variant: Given a Constrained Long Choice<\/jats:sc> instance, a process function that specifies the next beginning element depending on the current solution, and an iteration parameter \n \n $$\\varvec{T}$$<\/jats:tex-math>\n \n \n T<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, find \n \n $$\\varvec{T}$$<\/jats:tex-math>\n \n \n T<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n Long Choice<\/jats:sc> solutions satisfying the suitable conditions. We prove that this variant is \n \n $${{\\,\\mathrm{\\texttt{FP}}\\,}}^{{{\\,\\mathrm{\\texttt{PLC}}\\,}}}$$<\/jats:tex-math>\n \n \n \n \n \n FP<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:mrow>\n \n \n PLC<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-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 \n \n $${{\\,\\mathrm{\\texttt{PLC}}\\,}}$$<\/jats:tex-math>\n \n \n \n PLC<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-hard but also \n \n $${{\\,\\mathrm{\\texttt{PLS}}\\,}}$$<\/jats:tex-math>\n \n \n \n PLS<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>-hard, where the class \n \n $${{\\,\\mathrm{\\texttt{PLS}}\\,}}$$<\/jats:tex-math>\n \n \n \n PLS<\/mml:mi>\n \n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> 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.<\/jats:p>","DOI":"10.1007\/s00224-024-10209-4","type":"journal-article","created":{"date-parts":[[2024,12,27]],"date-time":"2024-12-27T09:27:22Z","timestamp":1735291642000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Note on Constrained Long Choice with Multiple Beginning Elements"],"prefix":"10.1007","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0418-8170","authenticated-orcid":false,"given":"Takashi","family":"Ishizuka","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,27]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Pasarkar, A., Papadimitriou, C.H., Yannakakis, M.: Extremal combinatorics, iterated pigeonhole arguments and generalizations of PPP. In: 14th Innovations in Theoretical Computer Science Conference. LIPIcs, vol. 251, pp. 88\u201318820 (2023). https:\/\/doi.org\/10.4230\/LIPICS.ITCS.2023.88","key":"10209_CR1","DOI":"10.4230\/LIPICS.ITCS.2023.88"},{"issue":"2","key":"10209_CR2","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N Megiddo","year":"1991","unstructured":"Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81(2), 317\u2013324 (1991). https:\/\/doi.org\/10.1016\/0304-3975(91)90200-L","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10209_CR3","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994). https:\/\/doi.org\/10.1016\/S0022-0000(05)80063-7","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"10209_CR4","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.: Settling the complexity of computing two-player nash equilibria. J. ACM 56(3), 14\u201311457 (2009). https:\/\/doi.org\/10.1145\/1516512.1516516","journal-title":"J. ACM"},{"issue":"2","key":"10209_CR5","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1145\/1461928.1461951","volume":"52","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a nash equilibrium. Commun. ACM 52(2), 89\u201397 (2009). https:\/\/doi.org\/10.1145\/1461928.1461951","journal-title":"Commun. ACM"},{"doi-asserted-by":"publisher","unstructured":"Filos-Ratsikas, A., Goldberg, P.W.: Consensus halving is ppa-complete. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 51\u201364 (2018). https:\/\/doi.org\/10.1145\/3188745.3188880","key":"10209_CR6","DOI":"10.1145\/3188745.3188880"},{"doi-asserted-by":"publisher","unstructured":"Deligkas, A., Fearnley, J., Melissourgos, T.: Pizza sharing is ppa-hard. In: Thirty-Sixth AAAI Conference on Artificial Intelligence, pp. 4957\u20134965 (2022). https:\/\/doi.org\/10.1609\/AAAI.V36I5.20426","key":"10209_CR7","DOI":"10.1609\/AAAI.V36I5.20426"},{"doi-asserted-by":"publisher","unstructured":"Goldberg, P.W., H\u00f8gh, K., Hollender, A.: The frontier of intractability for EFX with two agents. In: Algorithmic Game Theory - 16th International Symposium. Lecture Notes in Computer Science, vol. 14238, pp. 290\u2013307 (2023). https:\/\/doi.org\/10.1007\/978-3-031-43254-5_17","key":"10209_CR8","DOI":"10.1007\/978-3-031-43254-5_17"},{"unstructured":"Buresh-Oppenheim, J.: On the tfnp complexity of factoring (2006)","key":"10209_CR9"},{"issue":"2","key":"10209_CR10","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/J.JCSS.2015.08.001","volume":"82","author":"E Jer\u00e1bek","year":"2016","unstructured":"Jer\u00e1bek, E.: Integer factoring and modular square roots. J. Comput. Syst. Sci. 82(2), 380\u2013394 (2016). https:\/\/doi.org\/10.1016\/J.JCSS.2015.08.001","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"publisher","unstructured":"Sotiraki, K., Zampetakis, M., Zirdelis, G.: Ppp-completeness with connections to cryptography. In: 59th IEEE Annual Symposium on Foundations of Computer Science, pp. 148\u2013158 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00023","key":"10209_CR11","DOI":"10.1109\/FOCS.2018.00023"},{"doi-asserted-by":"publisher","unstructured":"Hub\u00e1cek, P., V\u00e1clavek, J.: On search complexity of discrete logarithm. In: 46th International Symposium on Mathematical Foundations of Computer Science. LIPIcs, vol. 202, pp. 60\u201316016 (2021). https:\/\/doi.org\/10.4230\/LIPICS.MFCS.2021.60","key":"10209_CR12","DOI":"10.4230\/LIPICS.MFCS.2021.60"},{"issue":"7\u20138","key":"10209_CR13","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1007\/s00153-015-0439-6","volume":"54","author":"P Pudl\u00e1k","year":"2015","unstructured":"Pudl\u00e1k, P.: On the complexity of finding falsifying assignments for herbrand disjunctions. Arch. Math. Log. 54(7\u20138), 769\u2013783 (2015). https:\/\/doi.org\/10.1007\/s00153-015-0439-6","journal-title":"Arch. Math. Log."},{"issue":"1","key":"10209_CR14","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988). https:\/\/doi.org\/10.1016\/0022-0000(88)90046-3","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"publisher","unstructured":"Daskalakis, C., Papadimitriou, C.H.: Continuous local search. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 790\u2013804 (2011). https:\/\/doi.org\/10.1137\/1.9781611973082.62","key":"10209_CR15","DOI":"10.1137\/1.9781611973082.62"},{"key":"10209_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/J.JCSS.2020.05.007","volume":"114","author":"J Fearnley","year":"2020","unstructured":"Fearnley, J., Gordon, S., Mehta, R., Savani, R.: Unique end of potential line. J. Comput. Syst. Sci. 114, 1\u201335 (2020). https:\/\/doi.org\/10.1016\/J.JCSS.2020.05.007","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"publisher","unstructured":"G\u00f6\u00f6s, M., Hollender, A., Jain, S., Maystre, G., Pires, W., Robere, R., Tao, R.: Further collapses in TFNP. In: 37th Computational Complexity Conference. LIPIcs, vol. 234, pp. 33\u201313315 (2022). https:\/\/doi.org\/10.4230\/LIPICS.CCC.2022.33","key":"10209_CR17","DOI":"10.4230\/LIPICS.CCC.2022.33"},{"key":"10209_CR18","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/J.JCSS.2017.12.003","volume":"94","author":"PW Goldberg","year":"2018","unstructured":"Goldberg, P.W., Papadimitriou, C.H.: Towards a unified complexity theory of total functions. J. Comput. Syst. Sci. Int. 94, 167\u2013192 (2018). https:\/\/doi.org\/10.1016\/J.JCSS.2017.12.003","journal-title":"J. Comput. Syst. Sci. Int."},{"doi-asserted-by":"publisher","unstructured":"Buresh-Oppenheim, J., Morioka, T.: Relativized NP search problems and propositional proof systems. In: 19th Annual IEEE Conference on Computational Complexity, pp. 54\u201367 (2004). https:\/\/doi.org\/10.1109\/CCC.2004.1313795","key":"10209_CR19","DOI":"10.1109\/CCC.2004.1313795"},{"unstructured":"Ishizuka, T.: Corrigendum: PLS is contained in PLC. Electron. Colloquium Comput. Complex. TR24-002 (2024). TR24-002","key":"10209_CR20"},{"doi-asserted-by":"publisher","unstructured":"Jain, S., Li, J., Robere, R., Xun, Z.: In pigeonhole principles and ramsey in TFNP. In: Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 406\u2013428 (2024). https:\/\/doi.org\/10.1109\/FOCS61266.2024.00033","key":"10209_CR21","DOI":"10.1109\/FOCS61266.2024.00033"},{"doi-asserted-by":"publisher","unstructured":"Fleming, N., Grosser, S., Pitassi, T., Robere, R.: Black-box PPP is not turing-closed. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024, pp. 1405\u20131414 (2024). https:\/\/doi.org\/10.1145\/3618260.3649769","key":"10209_CR22","DOI":"10.1145\/3618260.3649769"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10209-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10209-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10209-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:10:53Z","timestamp":1744132253000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10209-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,27]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10209"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10209-4","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,12,27]]},"assertion":[{"value":"7 October 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 December 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"2"}}