Consensus complexity ｜ Multi-prover Interactive Proof with commutative dynamic role swapping(dynamic MIP=NEXP)
Theme
No.1 : Which historical topology do we choice to reside?
historical tautology:Thales, Pytagoras, Euclid, Diophantus, Fermat,Pascal,Newton,Eular,Hamilton,Abel, Galois,Boole, Riemann, Maxwell, Cantor, Frege, Hilbert, Plank, Russell, Einstein, Markov, Noether, Dickson, Zermelo, Fraenkel, Banach, Tarski , Szilard, G ̈odel̈, Kolmogorov, Church, Turing, Oppenheimer, Von Neumann,Shannon, Callen-Welton, Landauer,Leech, Howard, Bennett
P vs NP : Cook, Levin, Chaitin, Martin-Löf,….Voevodsky, Lurie, Wigderson
No.2 how I descrive that topological manifold by algebraic geometry
Diophantine consensus: Byzantine→Probablistic(Arthur-Merlin)→pseudo randomness→randomness of RE
No.3 how I truncate that tautological topology into Diophantine fomula(or simple equation, geodesic)
topology class:P vs NP,NP→3-SAT, NP→ZKP, NP=PCP(log n, 1), IP=AMPoly=PSPACE,MIP=NEXP, MIP*=RE,BPP ⊆ BQP ⊆P#P
2IP prover-verifier role switching probabilistic bruteforce→RE以上？
Tiki-Taka of Zero Knowledge Proof
Reference
Thales of Miletus(B.C.624~)
Pythagoras(B.C.582~)
Euclid(B.C.325~)
Diophantus(200)
Pierre de Fermat(1607~)
Blaise Pascal(1623~)
Isaac Newton(1642~)
Leonhard Euler(1707~)
William Rowan Hamilton(1805~)
Niels Henrik Abel(1824) Mémoire sur les équations algébriques, où l’on démontre l’impossibilité de la résolution de l’équation générale du cinquième degré
Évariste Galois(1829/1846) Mémoire sur les conditions de résolubilité des équations par radicaux
https://www.numdam.org/item/JMPA_1846_1_11__381_0.pdf
George Boole(1847)The Mathematical Analysis of Logic, Being an Essay towards a Calculus of Deductive Reasoning
https://ia802801.us.archive.org/5/items/mathematicalanal00booluoft/mathematicalanal00booluoft.pdf
Bernhard Riemann Über die Hypothesen, welche der Geometrie zu Grunde liegen” (1854/1867) （On the Hypotheses which lie at the Bases of Geometry ）
https://www.emis.de/classics/Riemann/Geom.pdf
James Clerk Maxwell
https://www.math.ucdavis.edu/~temple/MAT22C/MaxwellOnPhysicalLinesOfForce.pdf
“A Dynamical Theory of the Electromagnetic Field” (1865)Philosophical Transactions of the Royal Society of London
On Physical Lines of Force https://www.bem.fi/library/1865-001.pdf
Theory of heat https://academicweb.nd.edu/~powers/ame.20231/maxwell1872.pdf
Georg Cantor(1874): Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen.
(On a property of the class of all real algebraic numbers)Journal für die Reine und Angewandte Mathematik
https://jamesrmeyer.com/pdfs/cantor-1874-ueber-eine-eigenschaft-des-inbegriffes.pdf
Sophus Lie(1874) Ueber Gruppen von Transformationen.” Nachrichten von der Königlichen Gesellschaft der Wissenschaften und der Georg-Augusts-Universität zu Göttingen, 1874
https://link.springer.com/chapter/10.1007/978-3-663-01390-7_1
Gottlob Frege(1879), Begriflsschriit, a formula language, modeled uponthat of arithmetic, for pure thought
https://logic-teaching.github.io/pred/texts/Frege%201967%20-%20Begriffsschrift.pdf
David Hilbert(1900) Mathematical ProblemsLecture delivered before the International Congress of
Mathematicians at Paris
https://www.aemea.org/math/Hilbert_23_Mathematical_Problems_1900.pdf
Max Plank(1900) Ueber eine Verbesserung der Wien’schen Spectralgleichung
https://www.ub.edu/hcub/hfq/sites/default/files/1900_Planck_VPG.pdf
Bertrand Russell(1903) Principles of Mathematics
https://www.finophd.eu/wp-content/uploads/2018/11/Russell-Principles-of-Mathematics.pdf
Albert Einstein(1905)Über einen die Erzeugung und Verwandlung des Lichtes betreffenden heuristischen Gesichtspunkt
https://onlinelibrary.wiley.com/doi/epdf/10.1002/andp.19053220607
Andrey Markov “Распространение закона больших чисел на величины, зависящие друг от друга” (1906) （Extension of the limit theorems of probability theory to a sum of variables connected in a chain）https://dspace.spbu.ru/items/088210fb-8460-489c-808c-05b4103f9963
“An Example of Statistical Investigation of the Text of ‘Eugene Onegin’ Illustrating the Dependence of Samples in a Chain” (1913) Bulletin de l’Académie Impériale des Sciences de St.-Pétersbourg
https://alpha60.de/research/markov/DavidLink_AnExampleOfStatistical_MarkovTrans_2007.pdf
Invariante Variationsprobleme” (1918) （Invariant Variation Problems ）Emmy Noether
Leonard Eugene Dickson(1919)On Quaternions and Their Generalization and the History of the Eight Square Theorem
https://www.jstor.org/stable/1967865?seq=17
Ludwig Wittgenstein(1921) Tractatus Logico-Philosophicus
https://www.gutenberg.org/files/5740/5740-pdf.pdf
Zermelo–Fraenkel set theory(1922)
https://user.math.uzh.ch/halbeisen/publications/pdf/brussels.pdf
Stefan Banach, Alfred Tarski “Sur la décomposition des ensembles de points en parties respectivement congruentes” (1924) （英訳: On the decomposition of sets of points into respectively congruent parts）Fundamenta Mathematicae
http://kielich.amu.edu.pl/Stefan_Banach/pdf/oeuvres1/12.pdf
Leo Szilard“Über die Entropieverminderung in einem thermodynamischen System durch Eingriffe intelligenter Wesen” (1929) （On the decrease of entropy in a thermodynamic system by the intervention of intelligent beings ）
Kurt G ̈odel̈(1931)UBER FORMAL UNENTSCHEIDBARE S ̈ATZE DER “PRINCIPIA MATHEMATICA” UND VERWANDTER SYSTEME I
https://www.w-k-essler.de/pdfs/goedel.pdf
Andray Kolmogorov”Grundbegriffe der Wahrscheinlichkeitsrechnung” (1933) （Foundations of the Theory of Probability）“Three approaches to the quantitative definition of information” (1965) Problems of Information Transmission
Alonzo Church(1936) An Unsolvable Problem of Elementary Number Theory
https://ics.uci.edu/~lopes/teaching/inf212W12/readings/church.pdf
Alan Turing(1936) ON COMPUTABLE NUMBERS, WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM
https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
J. R. OPPENHEIMER AND H. SNYDER(1939)On Continued Gravitational Contraction
https://the-center-of-gravity.com/documents/140/Oppenheimer-Snyder_On-continued-Gravitational-Contraction.pdf
Jon Von Neumann(1945) First draft of a report on the EDVAC
https://web.mit.edu/sts.035/www/PDFs/edvac.pdf
Claude Shannon(1948) A Mathematical Theory of Communication）
https://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf
Herbert B. Callen, Theodore A. Welton“Irreversiblity and generalized noise” (1951)
https://123.physics.ucdavis.edu/week_3_files/callen_irreversibility_and_noise_1951.pdf
Rolf Landauer“Irreversibility and Heat Generation in the Computing Process” (1961)
Ilya Prigogine, Paul Glansdorff“Thermodynamics of Irreversible Processes” (1967) / “Thermodynamic Theory of Structure, Stability and Fluctuations” (1971)
https://scispace.com/pdf/thermodynamics-of-irreversible-processes-the-experimental-tmzd1qteux.pdf
John Leech（1967）Notes on SPHERE PACKINGS
William A. Howard “The formulae-as-types notion of construction” (1969 / 1980) Essays on Combinatory Logic, Lambda Calculus and Formalisms
https://www.cs.cmu.edu/~crary/819-f09/Howard80.pdf
Charles H. Bennett“The Thermodynamics of Computation—A Review” (1982)
https://www.cpt.univ-mrs.fr/~verga/pdfs/Bennett-1982fk.pdf
Christopher Jarzynski A nonequilibrium equality for free energy differences (1997)
https://arxiv.org/pdf/cond-mat/9610209
Other modern mathematicians
Proof theory
P vs NP
Cook, S. A. (1971). “The complexity of theorem-proving procedures.” In Proceedings of the third annual ACM symposium on Theory of computing
https://dl.acm.org/doi/epdf/10.1145/800157.805047
Levin, L. A. (1973). “Universal search problems.” Problemy Peredachi Informatsii, 9(3)
https://www.karlin.mff.cuni.cz/~krajicek/levin.pdf
Gregory Chaitin“Information-Theoretic Computational Complexity” (1974)
https://www.cs.ox.ac.uk/activities/ieg/e-library/sources/ieee74.pdf
Per Martin-Löf“An Intuitionistic Theory of Types” (1975)
https://archive-pml.github.io/martin-lof/pdfs/An-Intuitionistic-Theory-of-Types-1972.pdf
Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co.
https://perso.limos.fr/~palafour/PAPERS/PDF/Garey-Johnson79.pdf
Gill (1977)Computational Complexity of Probabilistic Turing Machines
https://www.proquest.com/openview/ae9a6e6c19e75acb825b3b0ed2601d7a/1?pq-origsite=gscholar&cbl=666313
Lamport, L., Shostak, R., & Pease, M. (1982). “The Byzantine Generals Problem.” ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3),
https://lamport.azurewebsites.net/pubs/byz.pdf
Sipser (1983)
- “A Complexity Theoretic Approach to Randomness” (Sipser)
- https://dl.acm.org/doi/epdf/10.1145/800061.808762
ZKP (1985/1989) GMR85 Shafi Goldwasser,Silvio Micali, Charles Rackoff The Knowledge Complexity of Interactive Proof-Systems
https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf
NP=ZKP(1986) GMW86 O. Goldreich, S. Micali, A. Wigderson How to Prove All NP-Statements in Zero-Knowledge
https://dl.acm.org/doi/10.5555/36664.36675
MIP=NEXP
Babai, L., Fortnow, L., & Lund, C. (1991). “Non-deterministic exponential time has two-prover interactive protocols.” Computational Complexity,
https://lance.fortnow.com/papers/files/mip2.pdf
IP=PSPACE
Shamir, A. (1992). “IP = PSPACE.” Journal of the ACM (JACM), 39(4), 865-877.
https://dl.acm.org/doi/epdf/10.1145/146585.146609
Lund, C., Fortnow, L., Karloff, H., & Nisan, N. (1992). “Algebraic methods for interactive proof systems.” Journal of the ACM
https://dl.acm.org/doi/epdf/10.1145/146585.146605
Bernstein and Vazirani (1993 / 1997)
- “Quantum Complexity Theory”
- BPP ⊆ BQP ⊆P#P
- https://dl.acm.org/doi/epdf/10.1145/167088.167097
Nisan and Wigderson (1994)
- “Hardness vs Randomness
- https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf
Shor (1994 / 1997)
- “Algorithms for quantum computation: discrete logarithms and factoring”
- https://users.cs.duke.edu/~reif/courses/randlectures/Quantum.papers/shor.factoring.pdf
Impagliazzo and Wigderson (1997)
- “P = BPP unless E has sub-exponential circuits”
- https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW97/proc.pdf
Johan Håstad “Some Optimal Inapproximability Results” (STOC 1997 / J.ACM 2001)
https://www.cs.umd.edu/~gasarch/TOPICS/pcp/hastadopt.pdf
PCP定理における「定数（1）」を、「エラー確率を半分強に抑えながら、たったの3ビットをチェックするだけでよい」PCP1-ε, 1/2+ε(log n, 3)
Impagliazzo and Wigderson (1998)
- “Randomness vs Time: De-randomization under a uniform assumption”
- https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/IW98/proc.pdf
NP=PCP(log n, 1)
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998). “Proof verification and the hardness of approximation problems.”
https://dl.acm.org/doi/epdf/10.1145/278298.278306
Arora, S., & Safra, S. (1998). “Probabilistic checking of proofs: A new characterization of NP.” Journal of the ACM (JACM)
https://dl.acm.org/doi/epdf/10.1145/273865.273901
Janzing, Wocjan, and Beth (2002)
https://arxiv.org/pdf/quant-ph/0605181v2
Miltersen and Vinodchandran (2005)
- “Derandomizing Arthur-Merlin Games using Small-Space Generators”
- https://www.brics.dk/RS/99/47/BRICS-RS-99-47.pdf
Shaltiel and Umans (2005)
https://dl.acm.org/doi/epdf/10.1145/3055399.3055414
Gutfreund, Shaltiel, and Ta-Shma (2003 / 2007)
- “Uniform Hardness versus Randomness Tradeoffs for Arthur-Merlin Games”
- https://www.cs.tau.ac.il/~amnon/Papers/GST.cc.pdf
Aharonov, Jones, and Landau (2006)
https://arxiv.org/abs/quant-ph/0511096
Aaronson (2011)
- “BQP and the Polynomial Hierarchy”
- https://arxiv.org/pdf/0910.4698
Arvind, Gopal, Joglekar, and Kulkarni (2011) / Santhanam
- “Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds”
- https://pages.cs.wisc.edu/~baris/papers/AGHK11.pdf
Raz and Tal (2019)
- “Oracle Separation of BQP and PH”
- https://dl.acm.org/doi/epdf/10.1145/3313276.3316315
Vladimir Voevodsky(2013) Homotopy Type Theory
https://www.cs.uoregon.edu/research/summerschool/summer14/rwh_notes/hott-book.pdf
Jacob Lurie(2017) Higher Topos Theory
https://www.math.ias.edu/~lurie/papers/HTT.pdf
Avi Wigderson(2019) Mathematics and Computation
https://www.math.ias.edu/files/Book-online-Aug0619.pdf
MIP*=RE Ji, Z., Natarajan, A., Vidick, T., Wright, J., & Yuen, H. (2021). “MIP* = RE.” Communications of the ACM
https://arxiv.org/pdf/2001.04383
Dieter van Melkebeek and Nicollas Mocelin Sdroievski (2023 / 2024)
- “Leakage Resilience, Targeted Pseudorandom Generators, and Mild Derandomization of Arthur-Merlin Protocols”
- https://drops.dagstuhl.de/storage/00lipics/lipics-vol284-fsttcs2023/LIPIcs.FSTTCS.2023.29/LIPIcs.FSTTCS.2023.29.pdf
- “Instance-Wise Hardness versus Randomness Tradeoffs for Arthur-Merlin Protocols”
- https://drops.dagstuhl.de/storage/00lipics/lipics-vol264-ccc2023/LIPIcs.CCC.2023.17/LIPIcs.CCC.2023.17.pdf