Document Open Access Logo

Total Functions in the Polynomial Hierarchy

Authors Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, Christos Papadimitriou

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2021.44.pdf
  • Filesize: 0.6 MB
  • 18 pages

Document Identifiers

Author Details

Robert Kleinberg
  • Cornell University, Ithaca, NY, USA
Oliver Korten
  • Columbia University, New York, NY, USA
Daniel Mitropolsky
  • Columbia University, New York, NY, USA
Christos Papadimitriou
  • Columbia University, New York, NY, USA

Funding

  • Mitropolsky, Daniel: This research was supported in part by a grant from the Columbia-IBM center for Blockchain and Data Transparency, and by JPMorgan Chase & Co. This research was supported in part by NSF Awards CCF1763970 andCCF1910700, and by a research contract with Softbank
  • Papadimitriou, Christos: This research was supported in part by NSF Awards CCF1763970 andCCF1910700, and by a research contract with Softbank.

Acknowledgements

Many thanks to Noga Alon for a very enlightening conversation about the union bound, and to Omri Weinstein for an interesting discussion. The authors also thank Ofer Grossman and Eylon Yogev for useful discussions after the pre-print.

Cite AsGet BibTex

Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos Papadimitriou. Total Functions in the Polynomial Hierarchy. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 44:1-44:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ITCS.2021.44

Abstract

We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string that is far from all codewords, finding an explicit rigid matrix, as well as a problem we call Complexity, capturing Complexity Theory’s quest. When the union bound is generous, in that solutions constitute at least a polynomial fraction of the domain, we have a family of seemingly weaker classes α-PEPP, which are inside FP^NP|poly. Higher in the hierarchy, we identify the constructive version of the Sauer-Shelah lemma and the appropriate generalization of PPP that contains it, as well as the problem of finding a king in a tournament (a vertex k such that all other vertices are defeated by k, or by somebody k defeated).

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
Keywords
  • total complexity
  • polynomial hierarchy
  • pigeonhole principle

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Leonard Adleman. Two theorems on random polynomial time. In 19th Annual Symposium on Foundations of Computer Science, pages 75-83, 1978. URL: https://doi.org/10.1109/SFCS.1978.37.
  2. Noga Alon, Rina Panigrahy, and Sergey Yekhanin. Deterministic approximation algorithms for the nearest codeword problem. In Irit Dinur, Klaus Jansen, Joseph Naor, and José Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 339-351, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. Google Scholar
  3. Vikraman Arvind and Srikanth Srinivasan. Circuit lower bounds, help functions, and the remote point problem, 2009. URL: http://arxiv.org/abs/0911.4337.
  4. Vikraman Arvind and Srikanth Srinivasan. The remote point problem, small bias space, and expanding generator sets. In 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010, pages 59-70, 2010. Google Scholar
  5. Frank Ban, Kamal Jain, Christos H. Papadimitriou, Christos-Alexandros Psomas, and Aviad Rubinstein. Reductions in PPP. Inf. Process. Lett., 145:48-52, 2019. URL: https://doi.org/10.1016/j.ipl.2018.12.009.
  6. Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson. 2-source dispersers for sub-polynomial entropy and ramsey graphs beating the frankl-wilson construction. In Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, STOC '06, page 671–680, New York, NY, USA, 2006. Association for Computing Machinery. URL: https://doi.org/10.1145/1132516.1132611.
  7. Harry Buhrman, Lance Fortnow, Michal Koucký, John D. Rogers, and Nikolai K. Vereshchagin. Does the polynomial hierarchy collapse if onto functions are invertible? Theory Comput. Syst., 46(1):143-156, 2010. URL: https://doi.org/10.1007/s00224-008-9160-8.
  8. Gil Cohen. Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs, page 278–284. Association for Computing Machinery, New York, NY, USA, 2016. URL: https://doi.org/10.1145/2897518.2897530.
  9. Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a nash equilibrium. SIAM J. Comput., 39(1):195-259, 2009. URL: https://doi.org/10.1137/070699652.
  10. Aris Filos-Ratsikas and Paul W. Goldberg. Consensus halving is ppa-complete. In Ilias Diakonikolas, David Kempe, and Monika Henzinger, editors, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018, pages 51-64. ACM, 2018. URL: https://doi.org/10.1145/3188745.3188880.
  11. Paul W. Goldberg and Christos H. Papadimitriou. Towards a unified complexity theory of total functions. In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 37:1-37:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ITCS.2018.37.
  12. Pavel Hubácek, Moni Naor, and Eylon Yogev. The journey from NP to TFNP hardness. In Christos H. Papadimitriou, editor, 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, volume 67 of LIPIcs, pages 60:1-60:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. URL: https://doi.org/10.4230/LIPIcs.ITCS.2017.60.
  13. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC '97, page 220–229, New York, NY, USA, 1997. Association for Computing Machinery. URL: https://doi.org/10.1145/258533.258590.
  14. Ilan Komargodski, Moni Naor, and Eylon Yogev. White-box vs. black-box complexity of search problems: Ramsey and graph property testing. In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 622-632. IEEE Computer Society, 2017. URL: https://doi.org/10.1109/FOCS.2017.63.
  15. H. G. Landau. On dominance relations and the structure of animal societies: III The condition for a score structure. The bulletin of mathematical biophysics, 15(2):143-148, June 1953. URL: https://doi.org/10.1007/BF02476378.
  16. Stephen R. Mahaney. Sparse complete sets for NP: solution of a conjecture of berman and hartmanis. In 21st Annual Symposium on Foundations of Computer Science, Syracuse, New York, USA, 13-15 October 1980, pages 54-60. IEEE Computer Society, 1980. URL: https://doi.org/10.1109/SFCS.1980.40.
  17. Noam Nisan and Avi Widgerson. Hardness vs randomness. Journal of Computer and System Sciences, 49(2):149-167, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80043-1.
  18. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. Journal of Computer and System Sciences, 48(3):498-532, 1994. URL: https://doi.org/10.1016/S0022-0000(05)80063-7.
  19. N. Sauer. On the density of families of sets. J. Combinatorial Theory Ser. A, 13:145-147, 1972. URL: https://doi.org/10.1016/0097-3165(72)90019-2.
  20. C. E. Shannon. The synthesis of two-terminal switching circuits. The Bell System Technical Journal, 28(1):59-98, 1949. Google Scholar
  21. Saharon Shelah. A combinatorial problem; stability and order for models and theories in infinitary languages. Pacific J. Math., 41:247-261, 1972. URL: http://projecteuclid.org/euclid.pjm/1102968432.
  22. Katerina Sotiraki, Manolis Zampetakis, and Giorgos Zirdelis. Ppp-completeness with connections to cryptography. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 148-158. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00023.
  23. Luca Trevisan. Extractors and pseudorandom generators. J. ACM, 48(4):860–879, July 2001. URL: https://doi.org/10.1145/502090.502099.
  24. Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In Jozef Gruska, editor, Mathematical Foundations of Computer Science 1977, 6th Symposium, Tatranska Lomnica, Czechoslovakia, September 5-9, 1977, Proceedings, volume 53 of Lecture Notes in Computer Science, pages 162-176. Springer, 1977. URL: https://doi.org/10.1007/3-540-08353-7_135.
  25. V. N. Vapnik and A. Ja. Červonenkis. The uniform convergence of frequencies of the appearance of events to their probabilities. Teor. Verojatnost. i Primenen., 16:264-279, 1971. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact