NeoFronteras

Un investigador dice haber demostrado que los problemas tipo NP no pueden ser equivalentes a problemas tipo P.

¿Ha sido resuelto uno de los grandes enigmas de la computación? ¿Es todo problema de tipo NP igual a uno de tipo P? Según un investigador la respuesta es no.
La relación entre las clases de complejidad P y NP es estudiada por la teoría de la complejidad computacional que trata de los recursos (tiempo o memoria) requeridos durante un cálculo para resolver un problema dado. En esta teoría, la clase P contiene aquellos problemas de decisión que pueden ser resueltos con una máquina determinista secuencial (un ordenador) en un período de tiempo polinómico que es proporcional a los datos de entrada. Es decir, que si aumentamos los datos de entrada, el tiempo necesario para resolverlo no crece exponencialmente, sino más ñentamente. Este tipo de problemas son problemas “fáciles” y rápidos de resolver, como ordenar alfabéticamente un conjunto de palabras. Bajo esas mismas condiciones un problema NP no puede ser resuelto en un tiempo polinómico, sino en un tiempo exponencial, aunque sí se podría resolver rápidamente si se cuenta con una máquina (conceptual) no determinista. (leer más…)

Un nuevo modelo matemático explica cómo la aparición de rasgos nuevos permite aumentar la biodiversidad de los ecosistemas.

No sabemos muy bien por qué, pero la Matemáticas suelen ser el mejor lenguaje para describir la ciencia. No es solamente por su precisión, sino porque, sorprendentemente, la Naturaleza se deja describir bien matemáticamente. Hasta hace poco eran sólo las ciencias duras, como la Física, las que estaban descritas a base de Matemáticas. Esto se debía a que los procesos físicos son muy simples, aunque a primera vista no lo parezca. Los procesos biológicos, por el contrario, son muy complejos y no se dejan describir fácilmente por las Matemáticas. Además, la Biología era poco más o menos que una especie de “Filatelia” hasta hace poco, dedicada a coleccionar especies y hechos. Encima, en los estudios universitarios sobre ciencias biológicas había una escasa formación en Matemáticas, no habiendo tradición en ese campo. (leer más…)

Un modelo matemático predice que un control policial riguroso puede eliminar completamente los puntos calientes de crímenes de una clase, pero simplemente desplaza los de otro tipo.

Martin Short. Fuente: UCLA.

¿Le gusta la serie Numb3rs? Entonces quizás le agrade saber que la serie no está tan lejos de la realidad como en un principio se podría pensar.
El antropólogo Jeffrey Brantingham y los matemáticos Martin Short y Andrea Bertozzi, todos de la Universidad de California en Los Ángeles, han usado las Matemáticas para calcular cómo los movimientos de criminales y víctimas crean oportunidades para el crimen y cómo la policía puede reducir esta criminalidad.
Jeffrey Brantingham estudia además a los cazadores-recolectores del norte de Tíbet. Según él, los criminales se comportan esencialmente como cazadores-recolectores: forrajean en busca de oportunidades para cometer un crimen. El comportamiento de los cazadores-recolectores que les hace elegir entre un ñu y una gacela es el mismo tipo de cálculo que usa un criminal para elegir entre un Honda o un Lexus como objetivo de su crimen. (leer más…)

Descubren que las películas han evolucionado en el tiempo para que la duración se sus secuencias se ajusten al patrón de atención humano.

Las películas cinematográficas se montan a partir se muchas secuencias. Salvo que la película sea una excentricidad sueca, koreana, vietnamita o iraní, de esas que tanto gustan a los críticos y tanto torturan al público, normalmente se trata de mantener la atención de la audiencia administrando convenientemente la duración de esas secuencias. Los humanos somos unos seres que normalmente huimos del aburrimiento y nos podemos cansar de casi todo (incluso de nuestra pareja). Una película con todas las escenas de una duración determinada nos aburriría, independientemente del tiempo de duración de las escenas o de la propia película. (leer más…)

Un algoritmo cuántico permitiría resolver sistemas de ecuaciones lineales muy rápidamente.

La predición del tiempo meteorológico exige resolver sistemas de ecuaciones muy grandes. Fuente: University of Wisconsin-Madison.

Aunque la realización física de la computación cuántica es muy difícil y todavía no contamos con dispositivos que efectúen este tipo de computación de manera práctica, ya disponemos de algunos algoritmos que harán de estás máquinas las computadoras tan potentes que imaginamos, capaces de resolver exponencialmente rápido algunos de los problemas más duros. (leer más…)

Proponen un nuevo conjunto fractal que en tres dimensiones tiene una características similares al conjunto de Mandelbrot (que se define en 2 dimensiones) y al que llaman conjunto mandelbulb.

Conjunto mandelbulb. Foto: Daniel White.

Hay otros espacios a explorar que no son el espacio exterior. Son espacios abstractos habitados por objetos matemáticos. A veces su representación gráfica es increíblemente bella. Uno de los más famosos es el conjunto de Mabdelbrot que pertenece al plano complejo. Benoît Mandelbrot lo estudio en 1980 y por eso lleva su nombre, aunque en realidad éste fue descubierto por Pierre Fatou y Gaston Julia a principios del pasado siglo y representado por primera vez en 1978 Robert Brooks y Peter Matelski.
El conjunto de Mandelbrot, al estar contenido en el plano complejo, es plano. Sin embargo, posee una rica geometría. Es el arquetipo de fractal, de las figuras que son autosemejantes. Es decir, que cada parte, por pequeña que sea, tiene una forma similar a la de cualquier otra parte a cualquier escala. (leer más…)

Matemáticos de Norteamérica, Europa, Australia, y Sudamérica resolvieron el primer billón de casos de un antiguo problema de matemática.

El avance fue posible mediante una técnica ingeniosa para multiplicar números grandes. Los números involucrados son tan enormes que si sus dígitos fueran escritos a mano llegarían hasta la luna y volverían. El mayor desafío fue que esos números ni siquiera podían entrar en la memoria principal de las computadoras disponibles, por lo que los investigadores tuvieron que hacer un uso extenso de los discos duros de las computadoras.
Según Brian Conrey, Director del Instituto Americano de Matemática, “Problemas viejos como éste pueden parecer oscuros, pero generan un montón de investigación útil e interesante a medida que se desarrollan nuevas formas de atacarlos.” (leer más…)

Utilizan una computadora bacteriana para saber si un grafo es o no hamiltoniano. Esto sería una demostración para un nuevo tipo de computación.

Grafo hamiltoniano con uno de los posibles ciclos hamiltonianos marcado. Foto: Wikimedia C.

Quizás algunos de los temas más interesantes en la ciencia son los asuntos interdisciplinares, cuestiones que unen más de una rama del saber. Si a usted, amigo lector, se le dice que las Matemáticas pueden aplicarse a la Biología o a la Genética seguro que no se sorprenderá demasiado, al fin y al cabo las Matemáticas son el lenguaje de la ciencia. Pero, ¿y si es al revés?, ¿y si es la Genética la que ayuda a resolver problemas matemáticos?
Todo aquel que realmente esté interesado en la Informática (es decir, más allá de jugar con el ordenador y bajarse material de la red) sabe de la importancia de la Matemática Discreta. Esta rama de las Matemáticas permite estudiar la naturaleza de los números y, por tanto, desarrollar sistemas de cifrado, como el RSA que le permite conectarse de manera segura con su banco. (leer más…)

¿Cuántos sudokus hay? ¿Cuántas maneras hay de colorear los países de un mapa mundi? ¿Cómo organizar un festival de cine?

Izquierda: un mapa de Alemania (izquierda) y un sudoku (derecha) y sus representaciones en forma de grafos. Foto: Max Planck Institute for Dynamics and Self-Organization.

Antes de espantar a los posibles lectores de este artículo al mencionar la palabra “Matemáticas” recordemos que hay ramas de las Matemáticas, como la Matemática Discreta, que tienen aplicaciones directas en la vida cotidiana, constituyendo también parte de las bases de las ciencias de la computación. (leer más…)

La felicidad se propaga por la sociedad de manera similar a como lo haría una enfermedad contagiosa. A la felicidad le gusta la felicidad, la gente feliz tiende a estar junta y la gente con más contactos sociales felices es más feliz.

Desde hace siglos los filósofos han debatido sobre la felicidad. El ser humano ha dado varias definiciones para delimitar ese estado de dicha o gozo e incluso se han llegado a proponer varias recetas para alcanzarla, algunas de ellas basadas en dogmas religiosos, otras en la creación de paraísos artificiales de origen químico… Incluso en la constitución de los EEUU se recoge el derecho de todo ciudadano a perseguir la felicidad. País en el que sus habitantes tienen una particular obsesión por ser felices y lugar de origen del estudio que vamos a relatar a continuación y cuyos resultados son bastante interesantes. (leer más…)

Descubren los dos primos de Mersenne más grandes hasta la fecha. El mayor de ellos hace ganar 100.000 dólares al que lo encontró.

El proyecto Great Internet Mersenne Prime Search (GIMPS) ha anunciado el descubrimiento, no de uno, sino de dos números primos de Mersenne. El método empleado es el de la computación distribuida en la que muchos voluntarios permiten el uso de CPU de sus máquinas. No es la primera vez que se descubre un número primo de este tipo con este método por esta misma organización. El que ahora hace el número 46 es el número primo más grande conocido hasta la fecha. (leer más…)

Un modelo matemático parece explicar por qué existe el altruismo en la sociedad.

La razón por la que los humanos y otros organismos cooperan es un misterio, aunque gracias a esto se van creando sociedades más justas o se lucha por un bien común. Pero lo increíble es que se haga a costa del individuo que algunas veces no gana nada o incluso es penalizado por ello. Quizás el dicho de “ninguna buena acción se queda sin castigo” sea aplicable en algunos de estos casos.
Esta cuestión ha intrigado a los expertos durante siglos, especialmente desde que se sabe que la base de la evolución es la supervivencia de los mejor adaptados (o más bien el éxito reproductor). Bajo este punto de vista sería el egoísmo y no el altruismo el que se propagaría por la población. (leer más…)