¿P es igual a NP? Respuesta del Milenio. Método para Resolver Rompecabezas con el Algoritmo de Dios
Resumen
La complejidad de cualquier tipo de problemas puede ser desde lo más fácil hasta infinitamente complejo, hay problemas donde existen atajos con los algoritmos de Dios y se pueden resolver en tiempo polinómico en este caso NP está en P, y hay problemas que con los algoritmos de Dios no se resuelve en tiempo polinómico en este caso NP no está en P, cuando tengamos un problema lo resolveremos con el algoritmo más óptimo o con el algoritmo de Dios porque obviamente no existe un algoritmo mejor que el algoritmo de Dios, pueden existir 1, 2 o más algoritmo de Dios que resolverán el mismo problema con la misma cantidad de pasos, es imposible encontrar un algoritmo que resuelva el problema en menos pasos que el algoritmo de Dios. Obviamente si un algoritmo resuelve el problema en más pasos que el algoritmo de Dios entonces no es el algoritmo de Dios. Como resultado utilizamos el mejor algoritmo que es el algoritmo de Dios y observamos en cuantos pasos se resuelve este problema, si son muchos pasos o pocos pasos y tomamos la decisión si vale la pena dedicarle tiempo en resolver ese problema. Es imposible resolver el problema en menos pasos que la cantidad de pasos del algoritmo de Dios.
Descargas
Citas
A. S. Fraenkel and D. Lichtenstein, Computing a perfect strategy for n*n chess requires time exponential in n, Proc. 8th Int. Coll. Automata, Languages, and Programming, Springer LNCS 115 (1981) 278-293 and J. Comb. Th. A 31 (1981) 199-214.
Arvind, Vikraman; Kurur, Piyush P. (2006). "Graph isomorphism is in SPP". Information and Computation. 204 (5): 835–852.
Armar el Pyraminx Duo con el algoritmo de Dios.
Le enseñaremos cómo armar el cubo de Rubik y muchos otros rompecabezas en 3 dimensiones con el algoritmo de Dios. Nilson Bolívar (2020) 1-199 https://docs.google.com/document/d/10EgTFh2v-dWUFlGkP4GEldRg1ajbNIyg/edit?usp=sharing&ouid=115495646788988650320&rtpof=true&sd=true
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.
Colbourn, Charles J. (1984). "The complexity of completing partial Latin squares". Discrete Applied Mathematics. 8 (1): 25–30
Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158
Elvira Mayordomo. "P versus NP" Archived 16 February 2012 at the Wayback Machine Monografías de la Real Academia de Ciencias de Zaragoza 26: 57–68 (2004).
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.
Hartmanis, Juris. "Gödel, von Neumann, and the P = NP problem" (PDF). Bulletin of the European Association for Theoretical Computer Science. 38: 101–107.
I. Holyer (1981). "The NP-completeness of some edge-partition problems". SIAM J. Comput. 10 (4): 713–717.
Johnson, David S. (1987). "The NP-completeness column: An ongoing guide (edition 19)". Journal of Algorithms. 8 (2): 285–303.
Jump up to:a b Cook, Stephen (April 2000). "The P versus NP Problem" (PDF). Clay Mathematics Institute. Archived (PDF) from the original on 16 December 2013. Retrieved 18 October 2006.
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.
Ladner, R.E. (1975). "On the structure of polynomial time reducibility". Journal of the ACM. 22: 151–171 See Corollary 1.1.
P. T. Ledner "On the structure of polynomial time reducibility," Journal ACM, 22, pp. 151–171, 1975, Corollary 1.1
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.
William I. Gasarch (junio de 2002). «The P=?NP poll.». SIGACT News 33 (2): 34-47
Derechos de autor 2023 Nilson Rafael Bolívar Barrios
Esta obra está bajo licencia internacional Creative Commons Reconocimiento 4.0.
.jpg)
.png)
.png)
1.png)
