Revisiting MA vs. ∃ · BPP: A Functional Analogue

Ishizuka, Takashi

doi:10.51094/jxiv.577

##article.authors##

Ishizuka, Takashi Artificial Intelligence Laboratory, Fujitsu Limited https://orcid.org/0000-0003-0418-8170

DOI:

https://doi.org/10.51094/jxiv.577

キーワード:

Computational Complexity、 Probabilistic Verification、 Merlin-Arthur Model、 Search Problems、 TFNP

抄録

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.

利益相反に関する開示

There is no potential COI for the authors to disclose.

ダウンロード *前日までの集計結果を表示します

ダウンロード実績データは、公開の翌日以降に作成されます。

引用文献

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.