Consensus Algorithm by Interactive Proof with Commutative Dynamic Role Choice(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, Cantor, Frege, Hilbert, Plank, Russell, Einstein, Dickson, Zermelo, Fraenkel, G ̈odel̈, Charch, Turing, Oppenheimer, Von Neumann,Shannon, 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:NP,NP→3-SAT, NP→ZKP, NP=PCP(log n, 1), IP=AMPoly=PSPACE,MIP=NEXP, MIP*=RE
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
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
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
Zermelo–Fraenkel set theory(1922)
https://user.math.uzh.ch/halbeisen/publications/pdf/brussels.pdf
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
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
John Leech（1967）Notes on SPHERE PACKINGS
Other modern mathematicians
Proof theory
NP complete, 3-SAT 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
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
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
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
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
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
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