No hay resultados
Ver todos los resultados
  • Autenticarse
  • Registrarse
Red Nibö
Ciencia, cultura, conocimiento - nibö
  • Cs.Ambientales
    Desentrañando la contaminación en el aire a bajo costo

    Desentrañando la contaminación en el aire a bajo costo

    Registros congelados para orientar la adaptación al cambio climático en los Andes tropicales

    Registros congelados para orientar la adaptación al cambio climático en los Andes tropicales

    Dura advertencia del IPCC: “El mundo se enfrenta a múltiples e inevitables riesgos en las próximas dos décadas”

    Dura advertencia del IPCC: “El mundo se enfrenta a múltiples e inevitables riesgos en las próximas dos décadas”

    ¿Podría el calentamiento global provocar un enfriamiento brusco en el hemisferio norte? Una mirada a los climas del pasado para entender mejor el futuro

    ¿Podría el calentamiento global provocar un enfriamiento brusco en el hemisferio norte? Una mirada a los climas del pasado para entender mejor el futuro

    Los plásticos, una trampa para la vida silvestre

    Los plásticos, una trampa para la vida silvestre

    ¿Podemos predecir las sequías?

    ¿Podemos predecir las sequías?

    Las energías alternativas per se no solucionarán la crisis climática

    Las energías alternativas per se no solucionarán la crisis climática

    Cromosomas sexuales, insectos y una científica poco conocida

    Cromosomas sexuales, insectos y una científica poco conocida

  • Física.Química
    Giambiagi y Bollini: Los domadores del infinito

    Giambiagi y Bollini: Los domadores del infinito

    La complejidad del problema del milenio P vs NP y un algoritmo para su solución

    La complejidad del problema del milenio P vs NP y un algoritmo para su solución

    La geometría sagrada del Islam: un testimonio histórico de la armonía entre ciencia y religión

    La geometría sagrada del Islam: un testimonio histórico de la armonía entre ciencia y religión

    Confección post-fabricación a medida de transistores MoS2-FET

    Confección post-fabricación a medida de transistores MoS2-FET

    Astrónomas chilenas lideraron gran descubrimiento: Las huellas que deja la formación de los planetas

    Astrónomas chilenas lideraron gran descubrimiento: Las huellas que deja la formación de los planetas

    La (seria pero divertida) historia de la tabla periódica en su 150 aniversario

    La (seria pero divertida) historia de la tabla periódica en su 150 aniversario

    Biopolímeros magnéticos para la purificación de proteínas

    Biopolímeros magnéticos para la purificación de proteínas

    Los modelos matemáticos no predicen el futuro, pero ayudan a entenderlo

    Los modelos matemáticos no predicen el futuro, pero ayudan a entenderlo

  • Cs.Salud
    El estrés arruina muchas carreras científicas

    El estrés arruina muchas carreras científicas

    fertilidad

    Rose Frisch, la científica que relacionó la grasa corporal con la fertilidad femenina ante la hostilidad de sus colegas

    Sustancias que estimulan la comunicación verbal en los trastornos del espectro autista

    Sustancias que estimulan la comunicación verbal en los trastornos del espectro autista

    La vacuna contra la malaria: esperanza en medio de un gran reto que va más allá de la salud pública

    La vacuna contra la malaria: esperanza en medio de un gran reto que va más allá de la salud pública

    ¿Dónde están las variables de sexo y género en los estudios clínicos sobre la covid-19?

    ¿Dónde están las variables de sexo y género en los estudios clínicos sobre la covid-19?

    Cromosomas sexuales, insectos y una científica poco conocida

    Cromosomas sexuales, insectos y una científica poco conocida

    La vida secreta de las plaquetas

    La vida secreta de las plaquetas

    No hace falta trabajar tanto

    No hace falta trabajar tanto

  • Cs.Sociales
    El estrés arruina muchas carreras científicas

    El estrés arruina muchas carreras científicas

    Historia fuera de las cuatro paredes, una reflexión sobre una disciplina abierta

    Historia fuera de las cuatro paredes, una reflexión sobre una disciplina abierta

    ¿Cómo se transmite el conocimiento?

    ¿Cómo se transmite el conocimiento?

    Cronología breve del movimiento feminista en China

    Cronología breve del movimiento feminista en China

    Los precios de los alimentos subieron en todo el mundo un 40% durante el último año

    Los precios de los alimentos subieron en todo el mundo un 40% durante el último año

    No hace falta trabajar tanto

    No hace falta trabajar tanto

    Los Homo erectus con el cráneo más pequeño y el Homo habilis más reciente

    Los Homo erectus con el cráneo más pequeño y el Homo habilis más reciente

    Las dudas científicas que hacen daño

    Las dudas científicas que hacen daño

  • Tecnología.Web
    Tesla, o la utopía mentirosa de Elon Musk

    Tesla, o la utopía mentirosa de Elon Musk

    La complejidad del problema del milenio P vs NP y un algoritmo para su solución

    La complejidad del problema del milenio P vs NP y un algoritmo para su solución

    Nibö crea instancia de mastodon para la discusión sobre ciencia y tecnología

    Nibö crea instancia de mastodon para la discusión sobre ciencia y tecnología

    Ahora Facebook es Meta y vino a monetizar tu vida

    Ahora Facebook es Meta y vino a monetizar tu vida

    Los cinco colosos que sostienen la vida digital, cómo han llegado ahí y por qué se han vuelto peligrosos

    Los cinco colosos que sostienen la vida digital, cómo han llegado ahí y por qué se han vuelto peligrosos

    El oro de los tontos

    El oro de los tontos

    Los algoritmos también discriminan a los seres humanos: nosotros podemos impedirlo

    Los algoritmos también discriminan a los seres humanos: nosotros podemos impedirlo

    Confección post-fabricación a medida de transistores MoS2-FET

    Confección post-fabricación a medida de transistores MoS2-FET

  • Estudios.Género
  • Cs.Ambientales
    Desentrañando la contaminación en el aire a bajo costo

    Desentrañando la contaminación en el aire a bajo costo

    Registros congelados para orientar la adaptación al cambio climático en los Andes tropicales

    Registros congelados para orientar la adaptación al cambio climático en los Andes tropicales

    Dura advertencia del IPCC: “El mundo se enfrenta a múltiples e inevitables riesgos en las próximas dos décadas”

    Dura advertencia del IPCC: “El mundo se enfrenta a múltiples e inevitables riesgos en las próximas dos décadas”

    ¿Podría el calentamiento global provocar un enfriamiento brusco en el hemisferio norte? Una mirada a los climas del pasado para entender mejor el futuro

    ¿Podría el calentamiento global provocar un enfriamiento brusco en el hemisferio norte? Una mirada a los climas del pasado para entender mejor el futuro

    Los plásticos, una trampa para la vida silvestre

    Los plásticos, una trampa para la vida silvestre

    ¿Podemos predecir las sequías?

    ¿Podemos predecir las sequías?

    Las energías alternativas per se no solucionarán la crisis climática

    Las energías alternativas per se no solucionarán la crisis climática

    Cromosomas sexuales, insectos y una científica poco conocida

    Cromosomas sexuales, insectos y una científica poco conocida

  • Física.Química
    Giambiagi y Bollini: Los domadores del infinito

    Giambiagi y Bollini: Los domadores del infinito

    La complejidad del problema del milenio P vs NP y un algoritmo para su solución

    La complejidad del problema del milenio P vs NP y un algoritmo para su solución

    La geometría sagrada del Islam: un testimonio histórico de la armonía entre ciencia y religión

    La geometría sagrada del Islam: un testimonio histórico de la armonía entre ciencia y religión

    Confección post-fabricación a medida de transistores MoS2-FET

    Confección post-fabricación a medida de transistores MoS2-FET

    Astrónomas chilenas lideraron gran descubrimiento: Las huellas que deja la formación de los planetas

    Astrónomas chilenas lideraron gran descubrimiento: Las huellas que deja la formación de los planetas

    La (seria pero divertida) historia de la tabla periódica en su 150 aniversario

    La (seria pero divertida) historia de la tabla periódica en su 150 aniversario

    Biopolímeros magnéticos para la purificación de proteínas

    Biopolímeros magnéticos para la purificación de proteínas

    Los modelos matemáticos no predicen el futuro, pero ayudan a entenderlo

    Los modelos matemáticos no predicen el futuro, pero ayudan a entenderlo

  • Cs.Salud
    El estrés arruina muchas carreras científicas

    El estrés arruina muchas carreras científicas

    fertilidad

    Rose Frisch, la científica que relacionó la grasa corporal con la fertilidad femenina ante la hostilidad de sus colegas

    Sustancias que estimulan la comunicación verbal en los trastornos del espectro autista

    Sustancias que estimulan la comunicación verbal en los trastornos del espectro autista

    La vacuna contra la malaria: esperanza en medio de un gran reto que va más allá de la salud pública

    La vacuna contra la malaria: esperanza en medio de un gran reto que va más allá de la salud pública

    ¿Dónde están las variables de sexo y género en los estudios clínicos sobre la covid-19?

    ¿Dónde están las variables de sexo y género en los estudios clínicos sobre la covid-19?

    Cromosomas sexuales, insectos y una científica poco conocida

    Cromosomas sexuales, insectos y una científica poco conocida

    La vida secreta de las plaquetas

    La vida secreta de las plaquetas

    No hace falta trabajar tanto

    No hace falta trabajar tanto

  • Cs.Sociales
    El estrés arruina muchas carreras científicas

    El estrés arruina muchas carreras científicas

    Historia fuera de las cuatro paredes, una reflexión sobre una disciplina abierta

    Historia fuera de las cuatro paredes, una reflexión sobre una disciplina abierta

    ¿Cómo se transmite el conocimiento?

    ¿Cómo se transmite el conocimiento?

    Cronología breve del movimiento feminista en China

    Cronología breve del movimiento feminista en China

    Los precios de los alimentos subieron en todo el mundo un 40% durante el último año

    Los precios de los alimentos subieron en todo el mundo un 40% durante el último año

    No hace falta trabajar tanto

    No hace falta trabajar tanto

    Los Homo erectus con el cráneo más pequeño y el Homo habilis más reciente

    Los Homo erectus con el cráneo más pequeño y el Homo habilis más reciente

    Las dudas científicas que hacen daño

    Las dudas científicas que hacen daño

  • Tecnología.Web
    Tesla, o la utopía mentirosa de Elon Musk

    Tesla, o la utopía mentirosa de Elon Musk

    La complejidad del problema del milenio P vs NP y un algoritmo para su solución

    La complejidad del problema del milenio P vs NP y un algoritmo para su solución

    Nibö crea instancia de mastodon para la discusión sobre ciencia y tecnología

    Nibö crea instancia de mastodon para la discusión sobre ciencia y tecnología

    Ahora Facebook es Meta y vino a monetizar tu vida

    Ahora Facebook es Meta y vino a monetizar tu vida

    Los cinco colosos que sostienen la vida digital, cómo han llegado ahí y por qué se han vuelto peligrosos

    Los cinco colosos que sostienen la vida digital, cómo han llegado ahí y por qué se han vuelto peligrosos

    El oro de los tontos

    El oro de los tontos

    Los algoritmos también discriminan a los seres humanos: nosotros podemos impedirlo

    Los algoritmos también discriminan a los seres humanos: nosotros podemos impedirlo

    Confección post-fabricación a medida de transistores MoS2-FET

    Confección post-fabricación a medida de transistores MoS2-FET

  • Estudios.Género
No hay resultados
Ver todos los resultados
Ciencia, cultura, conocimiento - nibö
No hay resultados
Ver todos los resultados

La complejidad del problema del milenio P vs NP y un algoritmo para su solución

21/01/2022
en Tecnología.Web, Física.Química
CompartirTuitearCompartirCompartir

El problema P vs NP es uno de los grandes problemas en el mundo de las matemáticas aplicadas y la informática, o más precisamente en la teoría de la complejidad computacional. A pesar de que sus bases teóricas se remontan a Alan Turing, fue planteado paralelamente en los años 70, por los programadores Stephen Cook y Leonid Levin, convirtiéndose en uno de los “problemas del milenio” del famoso Instituto Clay de Matemáticas, que ofrece una recompensa de un millón de dólares a quien pueda solucionarlo. Sin embargo, ¿de qué trata el problema y cuál es su complejidad? ¿por qué es relevante o importante? ¿existe forma de resolverlo?

En este artículo, queremos ofrecerte respuestas a estas preguntas en dos partes bien diferenciadas. La primera, donde encontraras en lenguaje divulgativo los elementos más importantes que definen el problema, su complejidad e importancia y, la segunda, que contiene la propuesta realizada por el autor, de un algoritmo de solución para el problema de la suma de subconjuntos -perteneciente a la subclase NP Completo– que satisface necesaria y suficientemente la igualdad P= NP.

Dejamos a la valoración crítica de todos y todas, especialmente de la comunidad científica versada en la temática, los hallazgos producidos en nuestra investigación.

La complejidad del problema del milenio P vs NP

El problema P vs NP es  una de las preguntas más importantes en el campo de las ciencias de la computación, debido a las grandes repercusiones que habría, en caso de encontrarse una solución.

Su complejidad, esta relacionada con la TCC (teoría de la complejidad computacional), puesto que esta teoría -en sentido bastante simplificado-, persigue clasificar los problemas en aquellos que pueden o no ser resueltos con una cantidad determinada de recursos.

Estos recursos para efectos de dicha teoría son, tiempo y memoria. Es decir, el tiempo empleado durante determinado cálculo para resolver un problema dado y la memoria requerida para almacenar y procesar los datos del problema.

En nuestro mundo actual, sería sencillo suponer por intuición o lógica, que todos los problemas que se presenten a un ordenador pueden ser resueltos a pesar de cuán complejos sean.  Pero, ¿es realmente así?

Resulta que en  las matemáticas, al igual que en la informática, existen problemas que pueden o no tener solución, así mismo, en caso de existir alguna solución deben ser verificados, y esta requiere una utilización eficiente de recursos (tiempo y memoria) a través de algoritmos óptimos, donde preferiblemente  no se disponga de millones de años para solucionarlos.

Una forma práctica de imaginar el universo computacional y su complejidad así como su relación con el problema P vs NP (que explicaremos más adelante) es intentar ordenar y resolver un puzzle (rompecabezas). El puzzle aumentará su complejidad en la medida que se añadan más y más piezas, y por tanto el tiempo empleado para resolverlo podría llegar a ser abrumador; ¿pero, si existiera un algoritmo capaz de ordenar aquellas piezas en la menor cantidad de tiempo (tiempo polinómico= podría interpretarse como rápidez)?- ¿sería eso una solución al problema del puzzle? -Y ¿cómo lo comprobaríamos?- Su verificación para este ejemplo quizás sea más sencilla, ver un puzzle completo y resuelto es más simple que ordenar cada una de sus piezas; o como  opinaba Stephen Cook,… “hay problemas que sí pueden ser resueltos por un ordenador, solo que la máquina tardaría tanto, que el sol moriría antes”.

Así que el problema P vs NP, es algo más que un rompecabezas matemático abstracto. Su objetivo es determinar qué tipos de problemas se pueden resolver con ordenadores y cuáles no.

Si diluimos esta relación, encontraremos  que los problemas de clase “P” (de sus siglas en inglés “tiempo polinomial) , son “fáciles” de resolver para los ordenadores, es decir, las soluciones a estos problemas pueden ser calculadas en una cantidad de tiempo razonable, en comparación con la complejidad del problema. Por ejemplo, 22, es un problema P, todos podemos resolverlo en un tiempo considerablemente rápido (orden polinómico). Así que, aquellos problemas que podemos solucionar y verificar con un algoritmo de orden polinómico, lo llamaremos problema P.

No sucede así, para su entrañable relación con “NP” (de sus siglas en inglés “tiempo no determinista polinomial”), aquí su solución podría ser muy “difícil” de encontrar, quizá requeriría miles de millones de años de computación, pero una vez encontrada, es fácil de comprobar.

Esta clase de problema, es decir NP, se encuentran en un limbo informático en el que son considerados como ejercicios sin solución (indecidibles) e irresolubles (intratables). Son la base de la  seguridad  del cifrado en  criptografía , opera en modelos precisos de previsión financiera, en el análisis del comportamiento del pliegue de proteínas en una célula (como posible aplicación), y más cotidiano aún, en el juego  SUDOKU, o en la búsqueda de horarios de vuelos aéreos.

Juego Sudoku

Y luego está una relación aún más compleja, los problemas NP-Completos, que vienen siendo una especie de subclase a los NP ( es decir, están contenidos en la clase NP), estos se consideran problemas llave, porque si se encuentra una manera de resolver eficientemente solo uno (01)  de ellos, significa que todos -todos los NP– pueden resolverse eficientemente. Así que los ordenadores actuales, tomarían especies de “atajos” para la resolución de dichos problemas, en caso de comprobarse su igualdad.

Ejemplos como el del viajero, persiguen explicar con mejor suficiencia este embrollo. Imagina que eres un comerciante que debe entregar paquetes de mercancías en varias ciudades -conociendo la distancia entre ellas- y necesitas la ruta más corta y eficiente para visitarlas una sola vez, sin repetir y volver a tu punto de origen. ¿Cuántas posibles rutas puedes calcular y en cuánto tiempo? ¿cuál es la más eficiente? En dicho ejemplo, las respuestas a las preguntas planteadas se pueden verificar, pero requieren un tiempo ridículamente largo e imposible para resolverlas mediante cualquier procedimiento directo.

Podríamos empezar por calcular cada una de las posibilidades, pero eso llevaría mucho tiempo, como ya hemos reforzado suficientemente. Así que, este problema lo que pretende  demostrar es:

  1. ¿Es P diferente a NP?
  2. ¿Es P igual a NP?

El acervo científico actual nos dice que P es diferente a NP, pero no existe demostración alguna que corrobore ese planteamiento o lo contradiga. A no ser, que se empleen una  serie de pasos, como un algoritmo lo suficientemente capaz de solucionar y demostrar que P es igual a NP. ¿Será esto posible?

Veamos paso a paso, cómo el desarrollo de la investigación  nos plantea romper con el Santo Grial de las matemáticas, para beneficio de toda la comunidad científica a través de un algoritmo, que aporta una solución necesaria y suficiente a un problema NP-Completo,  como lo es la suma de subconjuntos.

Un algoritmo de solución  al problema NP- Completo

Recordemos que, el problema de la suma de subconjuntos pertenece a la categoría NP- completo (de acuerdo a la literatura científica existente) y su resolución- como problema llave- es equivalente a solucionar todos los de esta categoría. Para el desarrollo de dicho algoritmo- y su respectiva comprensión- iniciaremos con los siguientes enunciados, en forma de dos (02) planteamientos equivalentes, con el cual trabajaremos de ahora en adelante.

Planteamiento n°1:

Dado un conjunto de Enteros, ¿Existe algún subconjunto no vacío cuya suma sea exactamente igual a Cero?

Planteamiento n°2:

Dado un conjunto de Enteros y un Entero: S ¿Existe algún subconjunto cuya suma sea igual a: S?”

Ahora bien, si reducimos ese enunciado anterior, tenemos que:

Dado un conjunto de enteros: C cuya suma de sus elementos sea igual a: S” ¿Existe algún subconjunto: B perteneciente al conjunto: C cuya suma de los elementos del subconjunto: B sea igual a: S?

El próximo paso para llegar al algoritmo de solución, es diseñar dos criterios y certificados , que establezcan las condiciones necesarias y suficientes para tratar ambos planteamientos. El Criterio 1 permite abordar el Planteamiento 1 y el Criterio 2 tiene aplicación en el Planteamiento 2; la conjugación de ambos permite tratar el problema de la suma de subconjuntos.

Criterio 1: La condición necesaria y suficiente para que exista un subconjunto no vacío: B (Pero Nulo) perteneciente a un conjunto: A cuya suma sea igual a: S (A=S) Solo es necesario y suficiente que exista un subconjunto: C=S perteneciente al conjunto A, tal que: A – S = 0 y además que: A –  C = 0

Para demostrar el funcionamiento del Criterio 1 tenemos que:

                     A = {-7 , -3 , -2 , 5 , 8} = 1

                     S = 1

                     C = {-7, 8} = 1

                     B = {-3 , -2 , 5} = 0

                     A – S = {-7 , -3 , -2 , 5 , 8 , -1} = 0

                     S = C =  { -7 , -3 , -2 , 5 , 8 } = { -7 , 8 } = 1

Criterio 2: Para que exista un subconjunto no vacío ni nulo: C perteneciente a un conjunto: A cuya suma sea: S solo es necesario y suficiente que: A-C = B tal que: B sea un subconjunto no vacío ni nulo perteneciente a el conjunto: A

Un ejemplo, para el Criterio 2 es:

A = { -7 , -3 , -2 , 5 , 8 } = 1        A = { -7 , -3 , -2 , 5 , 8 } = 1

A = S = 1                                     A = S = 1

 C = 4                                           C = 3

 A – C = B = 1 – 4 = -3                A – C = B = 1 – 3 = -2

 B = -3                                           B = -2

 C = {5 , 8 , -7 , -2}  = 4                C = {-2 , 5}  = 3

Los criterios planteados, una vez analizados, sugieren un tratamiento efectivo al problema de la suma de subconjuntos, y esto nos permite, a su vez, proponer un pseudo código que logra transformar el problema de la suma de subconjuntos NP-completo a un problema NP y de igual forma de NP-completo a P. Presentamos pues, el siguiente algoritmo, el cual es ejecutable con lenguaje de programación Mat Lab R2020a.

Pseudocódigo del algoritmo Óptimo que permite demostrar que la suma de subconjunto está en: P

  • t=cputime (Tiempo de ejecución)
  • y=([10,-10,-5,16,-9]) (Conjunto de n elementos) (Entrada)
  • s=sum(y) (Función Suma de n elementos)
  • c=0 ó c=Cualquier entero (Constante o Parámetro de entrada)
  • x1=([y(1)])(Cualquiera de los 2n-1 Subconjuntos propios de la entrada)
  • sum(x1) (Función suma parcial del subconjunto propio)
  • s==sum(x1) (Salida lógica de existencia y comparación)
  • if ans==1 (Verificación y comprobación condicional (Criterio 1)
  •     A=([y(1)]) (Subconjunto)
  • B=([y(2) y(3) y(4) y(5)]) (Subconjunto complementario)
  •     disp(‘Existe un subconjunto: B=S’)(Criterio 1)
  •     disp(‘Existe un subconjunto: A=0’)(Criterio 1)
  •     break (Detención de la ejecución o rutina)(Bucle anidado)
  • else
  •     disp(‘No existe un subconjunto: B=S’)(Criterio 1)
  •     disp(‘No existe un subconjunto: A=0’)(Criterio 1)
  • end (Fin)
  • c==sum(x1) (Salida lógica de existencia y comparación)
  • if ans==1 (Verificación y comprobación condicional) (Criterio 2)
  • A=([y(1)])(Subconjunto)
  •     B=([y(2) y(3) y(4) y(5)]) (Subconjunto complementario)
  •     disp(‘Existe un subconjunto complementario: A1=0’)(Criterio 2)
  •     disp(‘Existe un subconjunto complementario: B=C’)(Criterio 2)
  •     break (Detención de la ejecución o rutina)(Bucle anidado)
  • else
  •     disp(‘No existe un subconjunto: A=0’)(Criterio 2)
  •     disp(‘No existe un subconjunto: B=C’)(Criterio 2)
  • end (Fin)

Fuente: Rodolfo Nieves (2022)

Ambas imagénes corresponden a la ejecución del algoritmo en lenguaje MatLab R2020a. Fuente: Rodolfo Nieves (2022)

El cumplimiento de la ahora  igualdad P=NP, a través del algoritmo presentado en el pseudo código, aporta una respuesta en orden polinómico al problema NP-completo, el cual invitamos sea evaluada, hasta en los espacios más escépticos. Por ahora, podemos agregar, que esperamos el pronunciamiento oficial del Instituto Clay sobre dicho algoritmo.

Después del algoritmo. ¿Qué sucederá?

Ciertamente no viviremos en otro universo -luego de la demostración suficiente y necesaria de dicho algoritmo- pero sí será posible quizás, estudiar a fondo algunas mutaciones en el ADN, o evaluar y hasta emular la forma en que se logran sintetizar algunas proteínas en nuestro organismo, entre otras diversas aplicaciones apasionantes y necesarias para nuestra sociedad. Una vez más, las matemáticas trascienden en otras áreas del conocimiento humano.


Para tener acceso al artículo científico original del Prof. Rodolfo Nieves, haz click aquí


Referencias bibliográficas

  • Richard M. Karp (1972). «Reducibility Among Combinatorial Problems». En R. E. Millern and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum.pp. 85–103. 
  • Stephen Cook (1971). «The Complexity of Theorem Proving Procedures».Proceedings of the third annual ACM symposium on Theory of computing. pp. 151–158. 
  • David Zuckerman (1996). «On Unapproximable Versions of NP-Complete   Problems».SIAM   Journal on Computing25 (6):  pp. 1293–1304. http://citeseer.ist.psu.edu/192662.html.   
  • G.B. Mathews, On the partition of numbers, Proceedings of the London Mathematical Society, 28:486-490, 1897.
  • T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, 2001.pter 35.5, The subset-sum problem.
  • Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, W.H. Freeman. ISBN 0716710455 A3.2: SP13, pg.223.
Etiquetas: algoritmocomplejidadinformáticamatemáticasNP CompletoP vs NPP=NPproblema del mileniosolución
Compartir12Tweet8CompartirEnviar
Artículo anterior

¿Cómo se transmite el conocimiento?

Próximo artículo

Historia fuera de las cuatro paredes, una reflexión sobre una disciplina abierta

Próximo artículo
Historia fuera de las cuatro paredes, una reflexión sobre una disciplina abierta

Historia fuera de las cuatro paredes, una reflexión sobre una disciplina abierta

Autor

Rodolfo Nieves

Matemático autodidacta.
Asociación Venezolana de Ciencias Naturales.

You do not have any posts.
Equipo editorial nibö
niboe.info
  • Desentrañando la contaminación en el aire a bajo costo
  • Giambiagi y Bollini: Los domadores del infinito
  • Registros congelados para orientar la adaptación al cambio climático en los Andes tropicales

Licencia de este artículo

Licencia Creative Commons
Esta obra está bajo una Licencia Creative Commons Atribución 4.0 Internacional.
  • Grandes esfuerzos se han hecho alrededor del mundo para reducir la contaminación atmosférica y tener ciudades más limpias. Esto ha hecho posible reducir eficientemente las emisiones de aerosoles emitidos por vehículos e industrias. Sin embargo, Quass et al. han encontrado que estos aerosoles estaban contrarrestando una buena parte del efecto de calentamiento de la atmósfera y, al ser removidos de ella, se ha incrementado el calentamiento en un 12% en 2019 comparado con el año 2000.

Fuente:
https://doi.org/10.5194/acp-2022-295

#ComunicaCiencia #DivulgaCiencia #CambioClimático #CrisisClimática
  • Despedimos el 2021 con estos extractos de los artículos más leídos este año en Nibö ✨

#ComunicaCiencia #DivulgaCiencia #NuestraCiencia
  • La Red Nibö ahora disponible para la discusión sobre ciencia y tecnología. 
https://red.niboe.info
  • El #fediverso no es una nueva red social, es una nueva forma de socializar online. El ecosistema de aplicaciones sociales del fediverso permite compartir contenidos desde distintas plataformas que se comunican entre sí, tal como lo hace tu email. Existen aplicaciones que pueden sustituir a twitter, instagram, facebook y youtube. Las aplicaciones del fediverso están desarrolladas bajo estándares libres y no colectan datos de sus usuarios para usarlos como fuente de ingresos económicos.

Ya más de 4 millones de personas están participando en el fediverso. Puedes unirte a cualquiera de sus aplicaciones, e incluso a la Red Nibö, una comunidad sobre ciencia y tecnología creada por el equipo de Nibö, disponible en https://red.niboe.info
  • Diversas sustancias pueden ayudar a estimular el habla en personas con trastornos del espectro autista. Conoce más detalles en esta revisión científica preparada por la @inmunologiatea para nibö.

#autismo #habla #comunicaciónverbal #tea #Omega3 #VitaminaB12 #DivulgaCiencia #ComunicaCiencia #NuestraCiencia #LatinxsEnCiencia #CienciaLatina
  • Bacterias que son arte. Esta vez te mostramos un par de cultivos de Klebsiella pneumoniae y Eschericha coli por la bioanalista @andrick_elen 🧫🦠

#bacteriología #bioanálisis #klebsiella #escherichiacoli #bacteria #CienciaLatina #NuestraCiencia #ComunicaCiencia #DivulgaCiencia #mujeresenciencia #mujeresenstem
Facebook Twitter Instagram Telegram Youtube

Nibö
Divulgación científica crítica, responsable e inclusiva.

TEMAS

  • Cs.Ambientales
  • Física.Química
  • Cs.Salud
  • Cs.Sociales
  • Tecnología.Web
  • Estudios.Género

NOSOTROS

  • Acerca de Nibö
  • Equipo editorial
  • Donaciones
  • Publica en Nibö
  • Contacto
  • Política de navegación

TWITTER

2022 | Artículos bajo licencia CC BY 4.0, a menos que se especifique otra licencia.

No hay resultados
Ver todos los resultados
  • Cs.Sociales
  • Cs.Salud
  • Cs.Ambientales
  • Física.Química
  • Tecnología.Web

2022 | Artículos bajo licencia CC BY 4.0, a menos que se especifique otra licencia.

¡Bienvenido!

o

Autenticarse a la cuenta siguiente

Recuperar contraseña Registrarse

Crear cuenta de usuario

o

Complete el formulario para registrarse

Todos los campos son requeridos Autenticarse

Obtener contraseña

Por favor indique su e-mail o nombre de usuario

Autenticarse
Este sitio web utiliza cookies. Si continúa utilizando este sitio web, está dando su consentimiento para el uso de cookies. Visite nuestra Política de privacidad y cookies.