Published in Volume XXIV, Issue 2, 2014, pages 177-216, doi: 10.7561/SACS.2014.2.177

Authors: U. Dal Lago, S. Zuppiroli, M. Gabbrielli

Abstract

We show that probabilistic computable functions, i.e., those func- tions outputting distributions and computed by probabilistic Turing machines, can be characterized by a natural generalization of Church and Kleene’s partial recursive functions. The obtained algebra, following Leivant, can be restricted so as to capture the notion of a polytime sampleable distribution, a key concept in average-case complexity and cryptography.

Full Text (PDF)

References

[1] Stephen Bellantoni and Stephen Cook. A new recursion-theoretic characterization of the polytime functions. Computational complexity, 2(2):97–110, 1992. http://dx.doi.org/10.1007/BF01201998 .

[2] Andrej Bogdanov and Luca Trevisan. Average-case complexity. Foundations and Trends in Theoretical Computer Science, 2(1):1–106, 2006. http://dx.doi.org/10.1561/0400000004 .

[3] Dorin Comaniciu, Visvanathan Ramesh, and Peter Meer. Kernel-based object tracking. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(5):564–577, 2003. http://dx.doi.org/10.1109/TPAMI.2003.1195991 .

[4] Nigel J. Cutland. Computability: An introduction to recursive function theory. Cambridge University Press, 1980.

[5] Ugo Dal Lago and Paolo Parisen Toldin. A higher-order characterization of probabilistic polynomial time. In Ricardo Pen˜a, Marko C. J. D. van Eekelen, and Olha Shkaravska, editors, Foundational and Practical Aspects of Resource Analysis (FOPARA 2011), volume 7177 of Lecture Notes in Computer Science, pages 1–18. Springer, 2011. http://dx.doi.org/10.1007/978-3-642-32495-6_1 .

[6] Ugo Dal Lago and Sara Zuppiroli. Probabilistic recursion theory and implicit computational complexity. In Gabriel Ciobanu and Dominique M´ery, editors, Proceedings of the 11th International Colloquium on Theoretical Aspects of Computing (ICTAC 2014), volume 8687 of Lecture Notes in Computer Science, pages 97–114. Springer, 2014. http://dx.doi.org/10.1007/978-3-319-10882-7_7 .

[7] Karel De Leeuw, Edward F Moore, Claude E Shannon, and Norman Shapiro. Computability by probabilistic machines. Automata studies, 34:183–198, 1956. http://dx.doi.org/10.1109/9780470544242.ch54 .

[8] John Gill. Computational complexity of probabilistic Turing ma- chines. SIAM Journal on Computing, 6(4):675–695, 1977. http://dx.doi.org/10.1137/0206049 .

[9] Jean-Yves Girard. Light linear logic. Information and Computation, 143(2):175–204, 1998. http://dx.doi.org/10.1006/inco.1998.2700 .

[10] Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of computer and system sciences, 28(2):270–299, 1984. http://dx.doi.org/10.1016/0022-0000(84)90070-9 .

[11] Jonathan Katz and Yehuda Lindell. Introduction to Modern Cryptogra- phy. Chapman and Hall/CRC Press, 2007.

[12] Stephen C. Kleene. General recursive functions of natural num- bers. Mathematische Annalen, 112(1):727–742, 1936. http://dx.doi.org/10.1007/bf01565439 .

[13] Daniel Leivant. Ramified recurrence and computational complex- ity I: Word recurrence and poly-time. In Peter Clote and Jef- freyB. Remmel, editors, Feasible Mathematics II, Progress in Com- puter Science and Applied Logic, pages 320–343. Springer, 1995. http://dx.doi.org/10.1007/978-1-4612-2566-9_11 .

[14] Daniel Leivant and Jean-Yves Marion. Lambda calculus characteriza- tions of poly-time. Fundamenta Informaticae, 19(1-2):167–184, 1993. http://dx.doi.org/10.1007/bfb0037112 .

[15] Christopher D. Manning and Hinrich Schu¨tze. Foundations of statistical natural language processing, volume 999. MIT Press, 1999.

[16] Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Morgan Kaufmann, 1988.

[17] Michael O. Rabin. Probabilistic automata. Information and control, 6(3):230–245, 1963. http://dx.doi.org/10.1016/s0019-9958(63)90290-0 .

[18] Michael O. Rabin and Dana Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):114–125, 1959. http://dx.doi.org/10.1147/rd.32.0114 .

[19] Eugene S. Santos. Probabilistic Turing machines and computability. Proceedings of the American Mathematical Society, 22(3):704–710, 1969. http://dx.doi.org/10.1090/s0002-9939-1969-0249221-4 .

[20] Eugene S. Santos. Computability by probabilistic Turing machines. Transactions of the American Mathematical Society, 159:165–184, 1971. http://dx.doi.org/10.2307/1996005 .

[21] Robert I. Soare. Recursively enumerable sets and degrees: a study of computable functions and computably generated sets. Perspectives in mathematical logic. Springer, 1987.

[22] Sebastian Thrun. Robotic mapping: A survey. In Gerhard Lakemeyer and Bernhard Nebel, editors, Exploring Artificial Intelligence in the New Millennium, pages 1–35. Morgan Kaufmann Publishers Inc., 2003.

Bibtex

@article{sacscuza:dal2014prtaicc,
  title={Probabilistic Recursion Theory and Implicit Computational Complexity},
  author={U. Dal Lago and S. Zuppiroli and M. Gabbrielli},
  journal={Scientific Annals of Computer Science},
  volume={24},
  number={2},
  organization={``A.I. Cuza'' University, Iasi, Romania},
  year={2014},
  pages={177--216},
  doi={10.7561/SACS.2014.2.177},
  publisher={``A.I. Cuza'' University Press}
}