Instinto Lógico

Recuerda que nadie debe pensar por tí.

Etiqueta: tamaño

P versus NP

P VS NPEs indudable que la complejidad computacional es una rama de las matemáticas/ informática que de suma importancia. Hay algunos problemas que son irresolubles por la gran cantidad de operaciones que se deberían realizar.

Cuando hacemos referencias a P y NP estamos haciendo referencia a la complejidad computacional.

Sin entrar engrandes disquisiciones matemáticas podemos definir varias clases de complejidad:

  • La clase P es el conjunto de todos los problemas resolubles en tiempo polinómico.
  • La clase EXP es el conjunto de todos los problemas resolubles en tiempo exponencial.
  • La clase PSPACE es el conjunto de todos los problemas resolubles en espacio polinómico.
  • La clase EXPSPACE es el conjunto de todos los problemas resolubles en espacio exponencial.

Por ejemplo el problema de determinar si un número es par o encontrar el camino más corto en un grafo se pueden resolver en tiempo y espacio polinómico, sin embargo muchos problemas sobre toma de decisiones o de combinatoria, como por ejemplo, el problema PERMUTACION: “dada una cadena de caracteres C sin caracteres repetidos, calcular todas las posibles permutaciones de los caracteres de C sólo se sabe resolver en tiempo exponencial en concreto n!

Formula de Stirling

Pero ¿a qué nos referimos cuando hablamos de NP? (más…)

Arenas, átomos y búsquedas. ¿De verdad son tan pequeños los átomos?

atomo en la manoMuchas veces hemos oído decir que los átomos son pequeños y que en una reducida cantidad de materia de la que manejamos en la vida cotidiana hay millones de ellos. Podemos hacer comparaciones a nuestro nivel macroscópico para comprender lo diminutos que son los átomos y las moléculas. Por ejemplo, podemos imaginar  que la relación que hay entre el tamaño de un átomo y una piedrecita es la misma que hay entre esa piedrecita y el planeta Tierra,  pero  pocos ejemplos pueden darnos una idea más impresionante del tamaño de los átomos que el que recogió E. Schrödinger (1887-1961) en su libro ¿Qué es la vida? (1944). El ejemplo ilustra el pequeño tamaño de los átomos (o mejor de las moléculas de agua), y que Schrödinger  recogió en su libro, se debe a W. Thomson (1824-1907), más conocido como Lord Kelvin y dice lo siguiente:

Supongamos que pudiéramos marcar las moléculas contenidas en un vaso de agua y teñirlas, por ejemplo de rojo, luego verter el contenido del vaso en el océano y agitar el agua de todos los océanos para conseguir que las moléculas se repartan uniformemente por los siete mares. Si después llenamos un vaso de agua de cualquier mar, en ese vaso habrá alrededor de un centenar de las moléculas que hemos marcado de rojo en nuestro primer vaso. (más…)

Instinto Lógico © 2014 Frontier Theme