{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T15:16:57Z","timestamp":1742397417070},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540210023"},{"type":"electronic","value":"9783540399100"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-39910-0_23","type":"book-chapter","created":{"date-parts":[[2014,3,18]],"date-time":"2014-03-18T02:40:04Z","timestamp":1395110404000},"page":"524-547","source":"Crossref","is-referenced-by-count":19,"title":["Computational Proof as Experiment: Probabilistic Algorithms from a Thermodynamic Perspective"],"prefix":"10.1007","author":[{"given":"Krishna V.","family":"Palem","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"23_CR1","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/321386.321395","volume":"14","author":"M Blum","year":"1967","unstructured":"M. Blum. A machine-independent theory of the complexity of recursive functions. Journal of the ACM, 14(2):322\u2013326, 1967.","journal-title":"Journal of the ACM"},{"unstructured":"L. Boltzmann. Further studies on the equilibrium distribution of heat energy among gas molecules. Viennese Reports, Oct. 1872.","key":"23_CR2"},{"key":"23_CR3","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1002\/cpa.3160310407","volume":"31","author":"GJ Chaitin","year":"1978","unstructured":"G. J. Chaitin and J. T. Schwartz. A note on monte carlo primality tests and algorithmic information theory. Communications on Pure and Applied Mathematics, 31:521\u2013527, 1978.","journal-title":"Communications on Pure and Applied Mathematics"},{"doi-asserted-by":"crossref","unstructured":"S. A. Cook. The complexity of theorem proving procedures. The Third Annual ACM Symposium on the Theory of Computing, pages 151-158, 1971.","key":"23_CR4","DOI":"10.1145\/800157.805047"},{"unstructured":"R. Feynman. Feynman Lectures on Computation. Addison-Wesley Publishing Company, 1996.","key":"23_CR5"},{"key":"23_CR6","first-page":"108","volume":"2","author":"JW Gibbs","year":"1876","unstructured":"J. W. Gibbs. On the equilibrium of heterogeneous substances. Transactions of the Connecticut Academy, 2:108\u2013248, 1876.","journal-title":"Transactions of the Connecticut Academy"},{"doi-asserted-by":"crossref","unstructured":"J. Hartmanis and R. E. Stearns. On the computational complexity of algorithms. Transactions of the American Mathematical Society, 117, 1965.","key":"23_CR7","DOI":"10.2307\/1994208"},{"issue":"2","key":"23_CR8","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R Karp","year":"1987","unstructured":"R. Karp and M. Rabin. Efficient randomized pattern matching algorithms. IBM Journal of Research and Development, 31(2):249\u2013260, 1987.","journal-title":"IBM Journal of Research and Development"},{"key":"23_CR9","volume-title":"Reducibility among combinatorial problems","author":"RM Karp","year":"1972","unstructured":"R. M. Karp. Reducibility among combinatorial problems. Plenum Press New York, 1972."},{"issue":"3","key":"23_CR10","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1287\/moor.2.3.209","volume":"2","author":"RM Karp","year":"1977","unstructured":"R. M. Karp. Probabilistic analysis of partitioning algorithms for the traveling-salesman problem in the plane. Mathematics of Operations Research,(USA), 2(3):209\u2013224, Aug. 1977.","journal-title":"Mathematics of Operations Research,(USA)"},{"key":"23_CR11","doi-asserted-by":"publisher","DOI":"10.1887\/0750307595","volume-title":"Maxwell\u2019s demon: Entropy, information, computing","author":"H Leff","year":"1990","unstructured":"H. Leff and A. F. Rex. Maxwell\u2019s demon: Entropy, information, computing. Princeton University Press, Princeton, N. J., 1990."},{"key":"23_CR12","first-page":"265","volume":"9","author":"LA Levin","year":"1973","unstructured":"L. A. Levin. Universal sorting problems. Problems of Information Transmission, 9:265\u2013266, 1973.","journal-title":"Problems of Information Transmission"},{"issue":"2","key":"23_CR13","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1145\/321510.321516","volume":"16","author":"Z Manna","year":"1969","unstructured":"Z. Manna. Properties of programs and the first-order predicate calculus. Journal of the ACM, 16(2):244\u2013255, 1969.","journal-title":"Journal of the ACM"},{"unstructured":"Z. Manna. Mathematical theory of computation. McGraw-Hill, 1974.","key":"23_CR14"},{"doi-asserted-by":"crossref","unstructured":"J. D. Meindl. Low power microelectronics: Retrospect and prospect. Proceedings of IEEE, pages 619-635, Apr. 1995.","key":"23_CR15","DOI":"10.1109\/5.371970"},{"doi-asserted-by":"crossref","unstructured":"R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.","key":"23_CR16","DOI":"10.1017\/CBO9780511814075"},{"unstructured":"K. Palem, S. Cheemalavagu, and P. Korkmaz. The physical representation of probabilistic bits (pbits) and the energy consumption of randomized switching. CREST Technical report, June 2003.","key":"23_CR17"},{"unstructured":"K. V. Palem. Thermodynamics of randomized computing: A discipline for energy aware algorithm design and analysis. Technical Report GIT-CC-02-56, Georgia Institute of Technology, Nov. 2002.","key":"23_CR18"},{"unstructured":"K. V. Palem. Energy aware computation: From algorithms and thermodynamics to randomized (semiconductor) devices. Technical Report GIT-CC-03-10, Georgia Institute of Technology, Feb. 2003.","key":"23_CR19"},{"unstructured":"K. V. Palem. Energy aware computing through randomized switching. Technical Report GIT-CC-03-16, Georgia Institute of Technology, May 2003.","key":"23_CR20"},{"unstructured":"C. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, 1994.","key":"23_CR21"},{"key":"23_CR22","doi-asserted-by":"publisher","first-page":"464","DOI":"10.2307\/2273415","volume":"XLV","author":"H Putnam","year":"1980","unstructured":"H. Putnam. Models and reality. Journal of Symbolic Logic, XLV:464\u2013482, 1980.","journal-title":"Journal of Symbolic Logic"},{"key":"23_CR23","volume-title":"Degree of difficulty of computing a function and a partial ordering of recursive sets. Technical Report 2","author":"MO Rabin","year":"1960","unstructured":"M. O. Rabin. Degree of difficulty of computing a function and a partial ordering of recursive sets. Technical Report 2, Hebrew University, Israel, 1960."},{"key":"23_CR24","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","volume":"12","author":"MO Rabin","year":"1980","unstructured":"M. O. Rabin. Probabilistic algorithm for testing primality. Journal of Number Theory, 12:128\u2013138, 1980.","journal-title":"Journal of Number Theory"},{"issue":"2","key":"23_CR25","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"M. O. Rabin and D. S. Scott. Finite automata and their decision problems. IBM Journal of Research and Development, 3(2):115\u2013125, 1959.","journal-title":"IBM Journal of Research and Development"},{"key":"23_CR26","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"J. T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM, 27:701\u2013717, 1980.","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"K.-U. Stein. Noise-induced error rate as limiting factor for energy per operation in digital ics. IEEE Journal of Solid-State Circuits, SC-31(5), 1977.","key":"23_CR27","DOI":"10.1109\/JSSC.1977.1050947"},{"doi-asserted-by":"crossref","unstructured":"A. Turing. On computable numbers, with an application to the entscheidungsproblem. In Proceedings of the London Mathematics Society, number 42 in 2, 1936.","key":"23_CR28","DOI":"10.1112\/plms\/s2-42.1.230"},{"doi-asserted-by":"crossref","unstructured":"H. von Baeyer. Maxwell\u2019s Demon: Why warmth disperses and time passes. Random House, 1998.","key":"23_CR29","DOI":"10.1063\/1.882553"},{"key":"23_CR30","volume-title":"Mathematical foundations of quantum mechanics","author":"J Neumann von","year":"1955","unstructured":"von Neumann J. Mathematical foundations of quantum mechanics. Princeton University Press, Princeton, N. J., 1955."},{"unstructured":"A. Whitehead and B. Russell. Principia Mathematica. Cambridge University Press, 1913.","key":"23_CR31"}],"container-title":["Lecture Notes in Computer Science","Verification: Theory and Practice"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-39910-0_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T07:41:08Z","timestamp":1558856468000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-39910-0_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540210023","9783540399100"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-39910-0_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}