Is P equal to NP? Answer and Method to solve puzzles with God's algorithm
¿Es P igual a NP? Respuesta y Método para resolver rompecabezas con el algoritmo de Dios
DOI:
https://doi.org/10.56712/latam.v4i6.1468Palabras clave:
god’s algorithm, complexity, solution, P, NPResumen
The complexity of any type of problem can be from the easiest to the infinitely complex, there are problems where there are shortcuts with God's algorithms and they can be solved in polynomial time, and there are problems where with God's algorithms there are no shortcuts and no are solved in polynomial time, if a non-deterministic Turing machine finds solutions to problems in polynomial time this means that a deterministic Turing machine with God's algorithm can also find solutions to the same problems in polynomial time, when we have a problem we will solve it with God's algorithm, we can have 1, 2 or more God's algorithms that solve the same problem with the same number of steps. As a result, we use God's algorithm, and we observe how many steps this problem is solved in. It can be many steps or few steps, and we make the decision if it is worth spending time to solve that problem. The author presented the results that it is impossible to solve the problem in fewer steps than the number of steps of God's algorithm.
Descargas
Citas
Arvind, Vikraman; Kurur, Piyush P. (2006). "Graph isomorphism is in SPP". Information and Computation. 204 (5):835–852 https://www.sciencedirect.com/science/article/pii/S089054010600023X?via%3Dihub
Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n × n chess requires time exponential in n". Journal of Combinatorial Theory. Series A. 31 (2): 199–214. https://www.sciencedirect.com/science/article/pii/0097316581900169?via%3Dihub
Colbourn, Charles J. (1984). "The complexity of completing partial Latin squares". Discrete Applied Mathematics. 8 (1): 25–30 https://www.sciencedirect.com/science/article/pii/0166218X84900751?via%3Dihub
Bolívar Nilson, Armar el Pyraminx Duo con el algoritmo de Dios. (Assemble the Pyraminx Duo with God's algorithm.)
Le enseñaremos cómo armar el cubo de Rubik y muchos otros rompecabezas en 3 dimensiones con el algoritmo de Dios. (We will teach you how to put together the Rubik's cube and many other 3-dimensional puzzles with God's algorithm.) https://docs.google.com/document/d/10EgTFh2v-dWUFlGkP4GEldRg1ajbNIyg/edit?usp=sharing&ouid=115495646788988650320&rtpof=true&sd=true
Bolívar Nilson, ¿P es igual a NP? Respuesta del milenio. Método para resolver rompecabezas con el algoritmo de Dios. Ciencia Latina Revista Científica Multidisciplinar Julio-agosto, 2023, Volumen 7, Número 4. 6028-6053 https://ciencialatina.org/index.php/cienciala/article/view/7393/11156
Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158
https://dl.acm.org/doi/10.1145/800157.805047
Davidson, Morley; Dethridge, John; Kociemba, Herbert; Rokicki, Tomas. «God's Number is 20» https://www.cube20.org/
Elvira Mayordomo. "P versus NP" Archived 16 February 2012 at the Wayback Machine Monografías de la Real Academia de Ciencias de Zaragoza( Monographs of the Zaragoza Royal Academy of Sciences ) 26: 57–68 (2004). https://web.archive.org/web/20120216154228/http://www.unizar.es/acz/05Publicaciones/Monografias/MonografiasPublicadas/Monografia26/057Mayordomo.pdf
Fischer, Michael J.; Rabin, Michael O. (1974). "Super-Exponential Complexity of Presburger Arithmetic". Proceedings of the SIAM-AMS Symposium in Applied Mathematics. 7: 27–41. Archived from the original on 15 September 2006. Retrieved 15 October 2017.
Fortnow, Lance (2009). "The status of the P versus NP problem" (PDF). Communications of the ACM. 52 (9): 78–86. CiteSeerX 10.1.1.156.767. doi:10.1145/1562164.1562186. S2CID 5969255. Archived from the original (PDF) on 24 February 2011. Retrieved 26 January 2010.
https://dl.acm.org/doi/10.1145/1562164.1562186
Hartmanis, Juris. "Gödel, von Neumann, and the P = NP problem" (PDF). Bulletin of the European Association for Theoretical Computer Science. 38: 101–107.
https://ecommons.cornell.edu/server/api/core/bitstreams/46aef9c4-288b-457d-ab3e-bb6cb1a4b88e/content
Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)". Journal of Algorithms. 8 (2): 285–303.
https://www.sciencedirect.com/science/article/abs/pii/0196677487900435?via%3Dihub
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke; Reed, Bruce (2012). "The disjoint paths problem in quadratic time". Journal of Combinatorial Theory. Series B. 102 (2): 424–435.
https://www.sciencedirect.com/science/article/pii/S0095895611000712?via%3Dihub
Ladner, R.E. (1975). "On the structure of polynomial time reducibility". Journal of the ACM. 22: 151–171 See Corollary 1.1. https://dl.acm.org/doi/10.1145/321864.321877
Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20
Valiant, Leslie G. (1979). "The complexity of enumeration and reliability problems". SIAM Journal on Computing. 8 (3): 410–421. https://epubs.siam.org/doi/10.1137/0208032
William I. Gasarch (junio de 20e02). «The P=?NP poll.». SIGACT News 33 (2): 34-47 https://www.cs.umd.edu/~gasarch/papers/poll.pdf
