% ============================================================================= % BibTeX Bibliography for: % "On the Thermodynamic Separation of P and NP: % Computational Irreversibility and the Landauer Barrier" % Author: Rafael D. De Paz % ============================================================================= % --- Core Complexity Theory --- @inproceedings{Cook1971, author = {Cook, Stephen A.}, title = {The Complexity of Theorem-Proving Procedures}, booktitle = {Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC)}, pages = {151--158}, year = {1971}, doi = {10.1145/800157.805047} } @incollection{Karp1972, author = {Karp, Richard M.}, title = {Reducibility Among Combinatorial Problems}, booktitle = {Complexity of Computer Computations}, publisher = {Plenum}, pages = {85--103}, year = {1972}, doi = {10.1007/978-1-4684-2001-2_9} } @article{Levin1973, author = {Levin, Leonid A.}, title = {Universal sequential search problems}, journal = {Problemy Peredachi Informatsii}, volume = {9}, number = {3}, pages = {115--116}, year = {1973} } @book{AroraBarakBook, author = {Arora, Sanjeev and Barak, Boaz}, title = {Computational Complexity: A Modern Approach}, publisher = {Cambridge University Press}, year = {2009}, isbn = {978-0-521-42426-4} } @book{Sipser2013, author = {Sipser, Michael}, title = {Introduction to the Theory of Computation}, publisher = {Cengage Learning}, year = {2013}, edition = {3rd} } @misc{ClayPNP, author = {{Clay Mathematics Institute}}, title = {P vs NP Problem}, year = {2000}, url = {https://www.claymath.org/millennium/p-vs-np/}, note = {Millennium Prize Problem, official problem statement by S.~Cook} } @article{CookStatement, author = {Cook, Stephen A.}, title = {The {P} versus {NP} Problem}, journal = {Clay Mathematics Institute Millennium Prize Problems}, year = {2000}, pages = {87--104}, url = {https://www.claymath.org/millennium/p-vs-np/} } % --- Thermodynamics of Computation --- @article{Landauer1961, author = {Landauer, Rolf}, title = {Irreversibility and Heat Generation in the Computing Process}, journal = {IBM Journal of Research and Development}, volume = {5}, number = {3}, pages = {183--191}, year = {1961}, doi = {10.1147/rd.53.0183} } @article{Bennett1973, author = {Bennett, Charles H.}, title = {Logical Reversibility of Computation}, journal = {IBM Journal of Research and Development}, volume = {17}, number = {6}, pages = {525--532}, year = {1973}, doi = {10.1147/rd.176.0525} } @article{Bennett1982, author = {Bennett, Charles H.}, title = {The Thermodynamics of Computation---A Review}, journal = {International Journal of Theoretical Physics}, volume = {21}, number = {12}, pages = {905--940}, year = {1982}, doi = {10.1007/BF02084158} } @article{BeruttEtAl2012, author = {B\'erut, Antoine and Arakelyan, Artak and Petrosyan, Artyom and Ciliberto, Sergio and Dillenschneider, Raoul and Lutz, Eric}, title = {Experimental verification of {L}andauer's principle linking information and thermodynamics}, journal = {Nature}, volume = {483}, pages = {187--189}, year = {2012}, doi = {10.1038/nature10872} } @article{Zurek1989, author = {Zurek, Wojciech H.}, title = {Algorithmic randomness and physical entropy}, journal = {Physical Review A}, volume = {40}, number = {8}, pages = {4731--4751}, year = {1989}, doi = {10.1103/PhysRevA.40.4731} } % --- One-Way Functions --- @article{DiffieHellman1976, author = {Diffie, Whitfield and Hellman, Martin E.}, title = {New Directions in Cryptography}, journal = {IEEE Transactions on Information Theory}, volume = {22}, number = {6}, pages = {644--654}, year = {1976}, doi = {10.1109/TIT.1976.1055638} } @article{ImpagliazzoWigderson1997, author = {Impagliazzo, Russell and Wigderson, Avi}, title = {{P} = {BPP} if {E} requires exponential circuits}, booktitle = {Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (STOC)}, pages = {220--229}, year = {1997}, doi = {10.1145/258533.258590} } @article{Impagliazzo1995, author = {Impagliazzo, Russell}, title = {A personal view of average-case complexity}, journal = {Proceedings of the 10th Annual Structure in Complexity Theory Conference}, pages = {134--147}, year = {1995}, doi = {10.1109/SCT.1995.514853} } % --- Kolmogorov Complexity --- @book{LiVitanyi2008, author = {Li, Ming and Vit\'anyi, Paul}, title = {An Introduction to {K}olmogorov Complexity and Its Applications}, publisher = {Springer}, year = {2008}, edition = {3rd}, doi = {10.1007/978-0-387-49820-1} } @article{Kolmogorov1965, author = {Kolmogorov, Andrey N.}, title = {Three Approaches to the Quantitative Definition of Information}, journal = {Problemy Peredachi Informatsii}, volume = {1}, number = {1}, pages = {3--11}, year = {1965} } % --- Physics and Computation --- @article{Aaronson2005, author = {Aaronson, Scott}, title = {{NP}-complete Problems and Physical Reality}, journal = {ACM SIGACT News}, volume = {36}, number = {1}, pages = {30--52}, year = {2005}, doi = {10.1145/1052796.1052804} } @book{AaronsonQCSD, author = {Aaronson, Scott}, title = {Quantum Computing Since Democritus}, publisher = {Cambridge University Press}, year = {2013}, isbn = {978-0-521-19956-8} } @article{Feynman1982, author = {Feynman, Richard P.}, title = {Simulating Physics with Computers}, journal = {International Journal of Theoretical Physics}, volume = {21}, number = {6-7}, pages = {467--488}, year = {1982}, doi = {10.1007/BF02650179} } % --- Second Law and Arrow of Time --- @article{Boltzmann1877, author = {Boltzmann, Ludwig}, title = {\"Uber die Beziehung zwischen dem zweiten Hauptsatze der mechanischen W\"armetheorie und der Wahrscheinlichkeitsrechnung}, journal = {Wiener Berichte}, volume = {76}, pages = {373--435}, year = {1877} } @book{Penrose1989, author = {Penrose, Roger}, title = {The Emperor's New Mind}, publisher = {Oxford University Press}, year = {1989}, isbn = {978-0-19-851973-7} } @book{Penrose2004, author = {Penrose, Roger}, title = {The Road to Reality: A Complete Guide to the Laws of the Universe}, publisher = {Vintage Books}, year = {2004}, isbn = {978-0-679-77631-4} } @article{Shannon1948, author = {Shannon, Claude E.}, title = {A Mathematical Theory of Communication}, journal = {Bell System Technical Journal}, volume = {27}, number = {3}, pages = {379--423}, year = {1948}, doi = {10.1002/j.1538-7305.1948.tb01338.x} } % --- Circuit Complexity --- @article{RazborovRudich1997, author = {Razborov, Alexander A. and Rudich, Steven}, title = {Natural Proofs}, journal = {Journal of Computer and System Sciences}, volume = {55}, number = {1}, pages = {24--35}, year = {1997}, doi = {10.1006/jcss.1997.1494} } @article{BakerGillSolovay1975, author = {Baker, Theodore and Gill, John and Solovay, Robert}, title = {Relativizations of the {P} = ?{NP} question}, journal = {SIAM Journal on Computing}, volume = {4}, number = {4}, pages = {431--442}, year = {1975}, doi = {10.1137/0204037} } @article{AaronsonWigderson2009, author = {Aaronson, Scott and Wigderson, Avi}, title = {Algebrization: A New Barrier in Complexity Theory}, journal = {ACM Transactions on Computation Theory}, volume = {1}, number = {1}, pages = {1--54}, year = {2009}, doi = {10.1145/1490270.1490272} }