Document Open Access Logo

Towards a Unified Complexity Theory of Total Functions

Authors Paul W. Goldberg, Christos H. Papadimitriou

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2018.37.pdf
  • Filesize: 0.58 MB
  • 20 pages

Document Identifiers

Author Details

Paul W. Goldberg
Christos H. Papadimitriou

Cite AsGet BibTex

Paul W. Goldberg and Christos H. Papadimitriou. Towards a Unified Complexity Theory of Total Functions. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ITCS.2018.37

Abstract

The class TFNP, of NP search problems where all instances have solutions, appears not to have complete problems. However, TFNP contains various syntactic subclasses and important problems. We introduce a syntactic class of problems that contains these known subclasses, for the purpose of understanding and classifying TFNP problems. This class is defined in terms of the search for an error in a concisely-represented formal proof. Finally, the known complexity subclasses are based on existence theorems that hold for finite structures; from Herbrand's Theorem, we note that such theorems must apply specifically to finite structures, and not infinite ones.
Keywords
  • Computational complexity
  • first-order logic
  • proof system
  • NP search functions
  • TFNP

Metrics

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

References

  1. Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi. The relative complexity of NP search problems. J. Comput. Syst. Sci., 57(1):3-19, 1998. URL: http://dx.doi.org/10.1006/jcss.1998.1575.
  2. Arnold Beckmann and Sam Buss. The NP search problems of frege and extended frege proofs. ACM Trans. Comput. Log., 18(2):11:1-11:19, 2017. URL: http://dx.doi.org/10.1145/3060145.
  3. Sam Buss. Bounded Arithmetic. Bibliopolis, Naples, Italy, 1986. URL: https://www.math.ucsd.edu/~sbuss/ResearchWeb/BAthesis/.
  4. Sam Buss. Quasipolynomial size proofs of the propositional pigeonhole principle. Theor. Comput. Sci., 576:77-84, 2015. URL: http://dx.doi.org/10.1016/j.tcs.2015.02.005.
  5. Samuel R. Buss. Polynomial size proofs of the propositional pigeonhole principle. Journal of Symbolic Logic, 52:916-927, 1987. Google Scholar
  6. Samuel R. Buss. On Herbrand’s Theorem. In Logic and Computational Complexity, volume 960 of Lecture Notes in Computer Science, pages 195-209. Springer, Berlin, Heidelberg, 1995. URL: https://www.math.ucsd.edu/~sbuss/ResearchWeb/herbrandtheorem/.
  7. Samuel R. Buss and Alan S. Johnson. Propositional proofs and reductions between NP search problems. Ann. Pure Appl. Logic, 163(9):1163-1182, 2012. URL: http://dx.doi.org/10.1016/j.apal.2012.01.015.
  8. Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player nash equilibria. J. ACM, 56(3):14:1-14:57, 2009. URL: http://dx.doi.org/10.1145/1516512.1516516.
  9. Stephen A. Cook and Robert A. Reckhow. The relative efficiency of propositional proof systems. J. Symb. Log., 44(1):36-50, 1979. Google Scholar
  10. 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: http://dx.doi.org/10.1137/070699652.
  11. Matthew Greaves. Classifying the computational complexity of the Ramsey and Factoring Problems. MSc dissertation, University of Oxford, 2017. Google Scholar
  12. Juris Hartmanis and Lane A. Hemachandra. Complexity classes without machines: On complete languages for UP. Theor. Comput. Sci., 58:129-142, 1988. URL: http://dx.doi.org/10.1016/0304-3975(88)90022-9.
  13. Jacques Herbrand. Recherches sur la théorie de la démonstration. 1930. URL: http://eudml.org/doc/192791.
  14. Pavel Hubácek, Moni Naor, and Eylon Yogev. The journey from NP to TFNP hardness. Electronic Colloquium on Computational Complexity (ECCC), 23:199, 2016. URL: http://eccc.hpi-web.de/report/2016/199.
  15. Emil Jeřábek. Approximate counting by hashing in bounded arithmetic. The Journal of Symbolic Logic, 74(3):829-860, 2009. Google Scholar
  16. Emil Jerábek. Integer factoring and modular square roots. J. Comput. Syst. Sci., 82(2):380-394, 2016. URL: http://dx.doi.org/10.1016/j.jcss.2015.08.001.
  17. Ilan Komargodski, Moni Naor, and Eylon Yogev. White-box vs. black-box complexity of search problems: Ramsey and graph property testing. Electronic Colloquium on Computational Complexity (ECCC), 24:15, 2017. URL: https://eccc.weizmann.ac.il/report/2017/015.
  18. Jan Krajíček. Bounded arithmetic, propositional logic, and complexity theory, volume 60 of Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 1995. Google Scholar
  19. Jan Krajícek. Implicit proofs. J. Symb. Log., 69(2):387-397, 2004. URL: http://dx.doi.org/10.2178/jsl/1082418532.
  20. Jan Krajícek and Pavel Pudlák. Some consequences of cryptographical conjectures for s^1_2 and EF. Inf. Comput., 140(1):82-94, 1998. URL: http://dx.doi.org/10.1006/inco.1997.2674.
  21. Nimrod Megiddo. A note on the complexity of P-matrix LCP and computing an equilibrium. Technical Report RJ6439, IBM Almaden Research Center, San Jose, 1988. Google Scholar
  22. Tsuyoshi Morioka. Classification of search problems and their definability in bounded arithmetic. Electronic Colloquium on Computational Complexity (ECCC), 8(082), 2001. URL: http://eccc.hpi-web.de/eccc-reports/2001/TR01-082/index.html.
  23. Christos H. Papadimitriou. On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci., 48(3):498-532, 1994. URL: http://dx.doi.org/10.1016/S0022-0000(05)80063-7.
  24. Pavel Pudlák. Ramsey’s theorem in bounded arithmetic. In Proceedings of the 4th Workshop on Computer Science Logic, CSL '90, pages 308-317, London, UK, UK, 1991. Springer LNCS 553. Google Scholar
  25. Pavel Pudlák. On the complexity of finding falsifying assignments for herbrand disjunctions. Arch. Math. Log., 54(7-8):769-783, 2015. URL: http://dx.doi.org/10.1007/s00153-015-0439-6.
  26. Ronald L. Rivest, Adi Shamir, and Leonard M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM, 21(2):120-126, 1978. URL: http://dx.doi.org/10.1145/359340.359342.
  27. Michael Sipser. On relativization and the existence of complete sets. In Proceedings of the 9th Colloquium on Automata, Languages and Programming, pages 523-531, London, UK, 1982. Springer-Verlag. 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