Revisiting MA vs. ∃ · BPP: A Functional Analogue
DOI:
https://doi.org/10.51094/jxiv.577Keywords:
Computational Complexity, Probabilistic Verification, Merlin-Arthur Model, Search Problems, TFNPAbstract
The complexity class TFNP, introduced by Megiddo and Papadimitriou (TCS 1991), has played a crucial role in computational complexity theory and some real applied fields. In this short paper, we will revisit the definition of the class of search problems in NP. Then, we formulate a probabilistic variant of TFNP (and also FNP). Finally, we propose a functional analog of MA vs. ∃ · BPP.
Conflicts of Interest Disclosure
There is no potential COI for the authors to disclose.Downloads *Displays the aggregated results up to the previous day.
References
László Babai. “Trading Group Theory for Randomness.” In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing. ACM, 1985, pp. 421–429.
Stephen A. Fenner, Lance Fortnow, Stuart A. Kurtz, and Lide Li. “An oracle builder’s toolkit.” In: Inf. Comput. 182.2 (2003), pp. 95–136.
Oded Goldreich and David Zuckerman. “Another Proof That BPP ⊆ PH (and More).” In: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. Vol. 6650. Lecture Notes in Computer Science. Springer, 2011, pp. 40–53.
Takashi Ishizuka. “On TFNP Classes: Approaches from Fixed Point Theory and Algorithmic Game Theory.” In: (2022).
Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos H. Papadimitriou. “Total Functions in the Polynomial Hierarchy.” In: 12th Innovations in Theoretical Computer Science Conference. Vol. 185. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 44:1–44:18.
Serge Massar and Miklos Santha. “Characterising the intersection of QMA and coQMA.” In: Quantum Inf. Process. 20.12 (2021), p. 396.
Serge Massar and Miklos Santha. “Total functions in QMA.” In: Quantum Inf. Process. 20.1 (2021), p. 35.
Nimrod Megiddo and Christos H. Papadimitriou. “On Total Functions, Existence Theorems and Computational Complexity.” In: Theoretical Computer Science 81.2 (1991), pp. 317–324.
Stathis Zachos and Martin Fürer. “Probabalistic Quantifiers vs. Distrustful Adversaries.” In: Foundations of Software Technology and Theoretical Computer Science. Vol. 287. Lecture Notes in Computer Science. Springer, 1987, pp. 443–455.
Downloads
Posted
Submitted: 2023-12-19 03:56:02 UTC
Published: 2023-12-22 04:22:49 UTC
License
Copyright (c) 2023
Takashi Ishizuka
This work is licensed under a Creative Commons Attribution 4.0 International License.
