Problema De Suma De Subconjuntos 2m5a6q

Índice general 1

Teoría de la complejidad computacional

1

1.1

Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

Problemas, algoritmos y complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.1

Problema computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.2

Problemas de decisión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.3

Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.2.4

Algoritmos de tiempo polinómico y problemas intratables . . . . . . . . . . . . . . . . . .

2

1.3

2

3

Clases de complejidad

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3.1

Definiendo clases de complejidad

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3.2

Máquinas de Turing deterministas y la clase P . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3.3

Computación no determinista y la clase NP . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.3.4

Clases de complejidad importantes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4

La pregunta P=NP

1.5

NP-Completitud

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.5.1

Reducción polinomial

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.5.2

Problemas NP-completos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.5.3

Importancia de la NP-Completitud . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.6

Haciendo frente a problemas NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.7

Véase también

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.8

Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.8.1

Artículos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.8.2

Libros de texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

NP-completo

6

2.1

Definición de NP-completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.2

Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

2.3

Ejemplos

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.4

Soluciones aproximadas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.5

Completitud bajo diferentes tipos de reducción . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.6

Véase también . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

2.7

Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8

Problema de decisión

10 i

ii

ÍNDICE GENERAL 3.1

Ejemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.2

Véase también

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.3

Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

4

Optimización (cómputo)

11

5

Problema de la mochila

12

5.1

Historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

5.2

Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

5.3

Simplificaciones y generalizaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

5.3.1

Problema de la mochila simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

5.3.2

Problema de la mochila de múltiple elección . . . . . . . . . . . . . . . . . . . . . . . . .

13

5.3.3

Problema de la mochila múltiple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

5.4

5.5 6

Métodos de resolución

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

5.4.1

Algoritmos voraces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

5.4.2

Algoritmos genéticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

Referencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

Problema de la mochila simple

15

6.1

Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

6.2

Resolución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

6.3

Aplicaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

6.3.1

Clave simétrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

15

6.3.2

Clave asimétrica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

6.4

Bibliografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

6.5

Texto e imágenes de origen, colaboradores y licencias . . . . . . . . . . . . . . . . . . . . . . . .

17

6.5.1

Texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

6.5.2

Imágenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

6.5.3

Licencia de contenido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

Capítulo 1

Teoría de la complejidad computacional La Teoría de la Complejidad Computacional es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo a su dificultad inherente, y en la relación entre dichas clases de complejidad.

Máquina de Turing demostró ser el modelo teórico correcto de cómputo. Sin embargo, rápidamente se descubrió que el modelo básico de la Máquina de Turing fallaba al cuantificar el tiempo y la memoria requerida por una computadora, un problema crítico hoy en día, y aún más en aquellos tiempos. La idea de medir el tiempo y espacio como una función de la longitud de la entrada, se originó a principios de los 60’s por Hartmanis and Stearns, y así, nació la teoría de la complejidad computacional.

Un problema se cataloga como “inherentemente difícil” si su solución requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado. La teoría de la complejidad computacional formaliza dicha aseveración, introduciendo modelos de cómputo matemáticos para el estudio de estos problemas y la En los inicios, los investigadores trataban de entender las cuantificación de la cantidad de recursos necesarios para nuevas medidas de complejidad, y cómo se relacionaban resolverlos, como tiempo y memoria. unas con otras. En 1965, Edmonds definió un “buen” alUno de los fines de la teoría de la complejidad compu- goritmo como uno con un tiempo de ejecución acotado tacional es determinar los límites prácticos de qué es por un polinomio, es decir, con un tiempo de ejecución lo que se puede hacer en una computadora y qué no. polinómico.[1] Esto condujo al surgimiento de uno de los Otros campos relacionados con la teoría de la compleji- conceptos más importantes de la teoría de la complejidad dad computacional son el análisis de algoritmos y la teoría computacional: la NP-completitud y su pregunta fundade la computabilidad. Una diferencia significativa entre mental, si P=NP. el análisis de algoritmos y la teoría de la complejidad El campo comenzó a florecer cuando el investigador computacional, es que el primero se dedica a determinar norteamericano Stephen Cook, trabajando de manela cantidad de recursos requeridos por un algoritmo en ra independiente al investigador soviético Leonid Leparticular para resolver un problema, mientras que la se- vin, probaron que existen problemas relevantes que son gunda, analiza todos los posibles algoritmos que pudieran NP-completos. En 1972, Richard Karp llevó esta idea ser usados para resolver el mismo problema. un paso más adelante, demostrando que 21 probleLa teoría de la complejidad computacional trata de clasificar los problemas que pueden, o no pueden ser resueltos con una cantidad determinada de recursos. A su vez, la imposición de restricciones sobre estos recursos, es lo que la distingue de la teoría de la computabilidad, la cual se preocupa por qué tipo de problemas pueden ser resueltos de manera algorítmica.

mas combinatorios y de teoría de grafos, caracterizados por ser computacionalmente intratables, eran NPcompletos.[2] También en los 70’s, se produjo un crecimiento de las clases de complejidad a medida que los investigadores trataban de comprender los distintos modelos de cómputo existentes.

En los 80’s, se produjo un auge de los modelos finitos, que analizaban el proceso de cómputo de una manera inherentemente distinta. Surgió un nuevo acercamiento a problemas como P=NP, y aún cuando estos modelos te1.1 Historia nían sus limitaciones separando las clases de complejidad, esta aproximación introdujo técnicas combinatorias Antes de que se realizaran investigaciones en torno a la que permitieron un mejor entendimiento de los límites complejidad de los algoritmos, se crearon los cimientos de estos modelos. de esta teoría por varios investigadores. Uno de los aportes más influyentes fue la definición de las Máquinas de Ya en los 90’s, se estudiaron nuevos modelos de cómputo Turing en 1936, las cuales resultaron ser una noción de como las computadoras cuánticas, donde una misma tacomputadora muy flexible y robusta. A medida que las rea puede tener diferente complejidad en la computación computadoras se desarrollaban en los 40’s y los 50’s, la clásica y en la computación cuántica. Sin embargo, exis1

2

CAPÍTULO 1. TEORÍA DE LA COMPLEJIDAD COMPUTACIONAL

ten varias limitantes, entre ellas, la de desarrollar un hard- 1.2.3 Algoritmos ware para este modelo, y que se requieren grandes cantidades de espacio para realizar los cálculos. Podemos decir informalmente, que los algoritmos son procedimientos paso-a-paso para resolver problemas. Se puede pensar en ellos como simples programas 1.2 Problemas, algoritmos y com- de computadora, escritos en un lenguaje artificial específico.[3]

plejidad

Se dice que un algoritmo resuelve un problema A, si dicho algoritmo se puede aplicar a cualquier instancia I de A, y Para poder referirnos a problemas como “inherentemense garantiza que siempre produce una solución para dicha te intratables” y problemas de dificultad “equivalente”, es instancia. De manera general, nos interesa encontrar el alnecesario comprender algunos términos más básicos. goritmo más “eficiente” para resolver cierto problema. En su sentido más amplio, la noción de eficiencia involucra a todos los recursos computacionales necesarios para la 1.2.1 Problema computacional ejecución de un algoritmo. Un problema computacional constituye una pregunta a ser Por algoritmo “más eficiente” usualmente nos referimos al respondida, teniendo generalmente varios parámetros, o más rápido. Debido a que los requerimientos de tiempo variables libres, cuyos valores no se han especificado. Un son usualmente un factor dominante cuando se trata de problema se describe mediante: determinar si un algoritmo es lo suficientemente eficiente para ser útil en la práctica, nos concentraremos en este 1. Una descripción general de todos sus parámetros recurso. (pueden ser de entrada o de salida). 2. Una sentencia que describa las propiedades que la respuesta, o la solución, debe cumplir. Una instancia de un problema se obtiene cuando se especifican valores particulares para todos los parámetros del problema. Por ejemplo, consideremos el problema del test de primalidad. La instancia es un número (e.g. 15) y la solución es “sí" si el número es primo, y “no” en caso contrario. Visto de otra manera, la instancia es una entrada particular del problema, y la solución es la salida correspondiente para la entrada dada.

1.2.4 Algoritmos de tiempo polinómico y problemas intratables Los científicos de la computación realizan la distinción entre algoritmos de Tiempo polinómico y algoritmos de tiempo exponencial cuando se trata de caracterizar a los algoritmos como “suficientemente eficiente” y “muy ineficiente” respectivamente.

Un algoritmo de tiempo polinomial se define como aquel con función de complejidad temporal en O(p(n)) para alguna función polinómica p, donde n denota el tamaño de la entrada. Cualquier algoritmo cuya función de comple1.2.2 Problemas de decisión jidad temporal no pueda ser acotada de esta manera, se Un problema de decisión es un tipo especial de problema denomina algoritmo de tiempo exponencial. computacional cuya respuesta es solamente “sí" o “no” (o, La mayoría de los algoritmos de tiempo exponencial son de manera más formal, “1” o “0”). simples variaciones de una búsqueda exhaustiva, mienUn problema de decisión pudiera verse como un lenguaje tras que los algoritmos de tiempo polinomial, usualmenformal, donde los elementos que pertenecen al lenguaje te se obtienen mediante un análisis más profundo de la son las instancias del problema cuya respuesta es “sí", los estructura del problema. En la teoría de la complejidad que no pertenecen al lenguaje son aquellas instancias cuya computacional, existe el consenso de que un problema no respuesta es “no”. El objetivo es decidir, con la ayuda de está “bien resuelto” hasta que se conozca un algoritmo de un algoritmo, si una determinada entrada es un elemento tiempo polinomial que lo resuelva. Por tanto, nos refedel lenguaje formal considerado. Si el algoritmo devuelve riremos a un problema como intratable, si es tan difícil como respuesta “sí", se dice que el algoritmo acepta la que no existe algoritmo de tiempo polinomial capaz de resolverlo.[4] entrada, de lo contrario se dice que la rechaza. Los problemas de decisión constituyen uno de los principales objetos de estudio de la teoría de la complejidad computacional, pues la NP-completitud se aplica directa1.3 Clases de complejidad mente a estos tipos de problemas en vez de a problemas de optimización. Estos problemas tienen gran importancia porque casi todo problema puede transformarse en un Una clase de complejidad es un conjunto de problemas que poseen la misma complejidad computacional. problema de decisión.

1.4. LA PREGUNTA P=NP

3

1.3.1

Definiendo clases de complejidad

1.3.2

Máquinas de Turing deterministas y paradas. Dada una instancia del problema I, la primera etapa simplemente “adivina” un candidato a solución S. la clase P

podido lograrse, es decir, no se conocen algoritmos que los resuelvan en tiempo polinómico. Quizás estos probleLas clases de complejidad más sencillas se definen te- mas tengan algoritmos en tiempo polinomial que se basan niendo en cuenta factores como: en principios por ahora desconocidos, o quizás estos problemas no pueden ser resueltos en tiempo polinómico, • El tipo de problema computacional: Los problemas debido a que son “inherentemente difíciles”. más comúnmente utilizados son los problemas de La clase de complejidad NP consta de los problemas “vedecisión, pero las clases de complejidad se pueden rificables” en tiempo polinómico. Por verificable se endefinir para otros tipos de problemas. tiende a un problema tal que dado un certificado de solución (candidato a solución), se puede verificar que di• El modelo de cómputo: El modelo de cómputo más cho certificado es correcto en un tiempo polinómico en común es la Máquina de Turing determinista, pero el tamaño de la entrada. A los problemas en la clase NP muchas clases de complejidad se basan en Máquiusualmente se les llama problemas NP.[6] nas de Turing no deterministas, Máquinas de Turing El término NP proviene de no determinista en tiempo pocuánticas, etc. linómico y se deriva de un caracterización alternativa de • El recurso (o recursos) que está(n) siendo acotado(s) esta clase, donde se utilizan Máquinas de Turing no dey la(s) cota(s): Estas dos propiedades usualmente se terministas. Informalmente, se puede definir la clase NP utilizan juntas, por ejemplo, “tiempo polinomial”, en términos de un algoritmo no determinista (recordar la “espacio logarítmico”, “profundidad constante”, etc. equivalencia entre algoritmo y Máquina de Turing). El algoritmo mencionado está compuesto por 2 etapas se-

Entonces, la etapa de verificación recibe como entrada a I y a S, y procede a realizar el cómputo de una manera deLa clase P contiene a aquellos problemas que son soluterminista, finalmente deteniéndose con la respuesta “sí", bles en tiempo polinómico por una máquina de Turing o con la respuesta “no”, o sigue computando sin detenerdeterminista.[5] se. Para la definición anterior se ha fijado el modelo de Al igual que la clase P, la clase NP es insensible a la eleccómputo: la Máquina de Turing determinista. Existen ción del modelo de cómputo no determinista, debido a distintas variantes de la Máquina de Turing y es conocique dichos modelos son equivalentes polinómicamente. do que la más débil de ellas puede simular a la más fuerte, adicionando a lo sumo un tiempo polinómico. En las décadas posteriores a la Tesis de Church-Turing surgieron otros modelos de cómputo, y se pudo mostrar que la 1.3.4 Clases de complejidad importantes Máquina de Turing también podía simularlos a lo sumo adicionando también un tiempo polinómico. Por tanto, la Muchas clases de complejidad importantes pueden ser clase análoga a P para dichos modelos no es mayor que definidas acotando el tiempo o el espacio utilizado por la clase P para el modelo de cómputo de la máquina de el algoritmo. Algunas de estas clases de problemas de decisión son: Turing. La clase P juega un papel importante en la teoría de la complejidad computacional debido a que:

1.4 La pregunta P=NP

1. P es invariante para todos los modelos de cómputo que son polinómicamente equivalentes a la Máquina La relación entre las clases P y NP es fundamental para la teoría de la NP-completitud. Intuitivamente, creemos de Turing determinista. que P es un subconjunto de NP. Y efectivamente, cada 2. A grandes rasgos, P corresponde a la clase de pro- problema de decisión resuelto por un algoritmo de tiemblemas que, de manera realista, son solubles en una po polinomial determinista, también puede ser resuelto computadora. por un algoritmo de tiempo polinomial no determinista. Simplemente se necesita observar que cualquier algoritmo determinista puede ser utilizado en la etapa de ve1.3.3 Computación no determinista y la rificación de un algoritmo no determinista. Si B es un problema de P, y A es un algoritmo de tiempo polinoclase NP mial para B, entonces se puede construir un algoritmo de Muchas veces podemos evitar utilizar la fuerza bruta en tiempo polinomial no determinista para B, simplemente los problemas para obtener soluciones en tiempo polinó- utilizando A en la etapa de verificación e ignorando la etamico. Sin embargo, para algunos problemas esto no ha pa de adivinación. Por tanto, si B pertenece a P, entonces

4

CAPÍTULO 1. TEORÍA DE LA COMPLEJIDAD COMPUTACIONAL

B también pertenece a NP. La pregunta P=NP es una de las más importantes en el campo de las ciencias de la computación, debido a las grandes repercusiones que habrían, en caso de encontrarse una solución. Si P=NP, cualquier problema polinómicamente verificable fuera polinómicamente decidible. La mayoría de los investigadores creen que estas clases no son iguales, porque se han realizado bastantes esfuerzos para encontrar algoritmos de tiempo polinomial para varios problemas en NP, sin éxito. Los investigadores también han tratado de probar que las clases son distintas, pero eso conllevaría a mostrar que no existe un algoritmo “eficiente” para reemplazar a la búsqueda por fuerza bruta.

1.5 NP-Completitud 1.5.1

Reducción polinomial

Una reducción es una transformación de un problema en otro problema. Intuitivamente, un problema Q puede ser reducido a otro problema Q', si cualquier instancia del problema Q puede ser “fácilmente” expresada como una instancia del problema Q', y cuya solución proporcione una solución para la instancia de Q.[7]

1.5.3 Importancia de la NP-Completitud Quizás la razón de mayor peso por la cual los científicos de la computación creen que P es distinto de NP, es la existencia de la clase de problemas “NP-completos”. Esta clase tiene la curiosa propiedad de que si algún problema NP-completo puede ser resuelto en tiempo polinomial, entonces todo problema en NP tiene una solución en tiempo polinomial, es decir, P=NP. A pesar de años de estudio, ningún algoritmo de tiempo polinomial se ha descubierto para ningún problema NP-completo. Desde el punto de vista teórico, un investigador intentando mostrar que la clase P es distinta de la clase NP, pudiera enfocarse en un problema NP-completo. Si algún problema en NP requiere más que un tiempo polinomial, entonces uno NP-completo también. Además, un investigador intentando demostrar que P=NP, solo necesita encontrar un algoritmo de tiempo polinomial para un problema NP-completo para lograrlo. Desde el punto de vista práctico, el fenómeno de la NPcompletitud puede prevenir la pérdida de tiempo cuando se busca un algoritmo de tiempo polinomial no existente para resolver un problema determinado. Aún cuando no se posean los elementos matemáticos para demostrar que cierto problema no se puede resolver en tiempo polinomial, creemos que P no es igual a NP, así que demostrar que el problema es NP-completo, es una fuerte evidencia de su no “polinomialidad”.

Existen muchos tipos de reducciones: basadas en el método de reducción, como las reducciones de Cook, las reducciones de Karp y las reducciones de Levin, y las basadas en la cota de la complejidad, como la reducción en 1.6 Haciendo frente a problemas tiempo polinomial o la reducción de espacio logarítmiNP ca. Una de las reducciones más utilizadas es la reducción en tiempo polinomial, lo cual significa que el proceso de reducción toma un tiempo polinomial. Teniendo en cuenta la definición de problema intratable, si no se cumple que P=NP, entonces los problemas NPcompletos son intratables.

1.5.2

Problemas NP-completos

Las reducciones en tiempo polinomial nos dotan de elementos para probar, de una manera formal, que un problema es al menos tan difícil que otro, con una diferencia de un factor polinomial. Estas son esenciales para definir a los problemas NP-completos, además de ayudar a comprender los mismos. La clase de los problemas NP-completos contiene a los problemas más difíciles en NP, en el sentido de que son los que estén más lejos de estar en P. Debido a que el problema P=NP no ha sido resuelto, el hecho de reducir un problema B, a otro problema A, indicaría que no se conoce solución en tiempo polinomial para A. Esto es debido a que una solución en tiempo polinomial para A, tendría como consecuencia la existencia de una solución polinomial para B. De manera similar, debido a que todos los problemas NP pueden ser reducidos a este conjunto, encontrar un problema NP-completo que pueda ser resuelto en un tiempo polinomial significaría que P=NP.

Muchos problemas de la práctica son NP-completos, y son muy importantes como para desistir simplemente porque no sabemos cómo encontrar una solución óptima en tiempo polinomial. Aún si un problema es NPcompleto, pueden haber esperanzas. Existen tres estrategias fundamentales para lidiar con un problema NPcompleto: • Si la entrada es pequeña, un algoritmo con tiempo de ejecución exponencial pudiera ser perfectamente aceptable. • Se pudieran aislar algunos casos especiales que se pudieran resolver en tiempo polinomial. • Podríamos utilizar aproximaciones para encontrar soluciones lo suficientemente cercanas al óptimo en tiempo polinomial. En la práctica, obtener soluciones cercanas al óptimo es bastante aceptable. A estos

1.8. REFERENCIAS

5

algoritmos se les denomina algoritmos de aproxima- 1.8.2 Libros de texto ción, y en muchos casos se apoyan en heurísticas y • Arora, Sanjeev; Barak, Boaz (2009), metaheurísticas. Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4, http://www.cs.princeton.edu/theory/complexity/ 1.7 Véase también • Reducción (complejidad) • Teorema de Cook-Levin • Lista de 21 problemas NP-completos de Karp • Clases de complejidad P y NP • Teorema de la jerarquía temporal • Computación cuántica

1.8 Referencias [1] Richard M. Karp, “Combinatorics, Complexity, and Randomness”, 1985 Turing Award Lecture. [2] Richard M. Karp (1972), «Reducibility Among Combinatorial Problems», en R. E. Miller and J. W. Thatcher (editors), Complexity of Computer Computations, New York: Plenum, pp. 85–103. [3] Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman, (page 4). [4] Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman, (page 8). [5] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3.ª edición, MIT Press and McGraw-Hill, (page 1049). [6] Garey, Michael R., Johnson David S., (1979), Computers and Intractability: A Guide to the Theory of NPCompleteness, W. H. Freeman, (page 28). [7] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford, (2010), Introduction to Algorithms, 3.ª edición, MIT Press and McGraw-Hill, (page 1067).

1.8.1

Artículos

• Cook, Stephen (1983), «An overview of computational complexity», Commun. ACM (ACM) 26 (6): 400–408, ISSN 0001-0782 • Fortnow, Lance; Homer, Steven (2002), «A Short History of Computational Complexity», Bulletin of the EATCS 80: 95–133, http://people.cs.uchicago. edu/~{}fortnow/papers/history.pdf

• Sipser, Michael (2006), Introduction to the Theory of Computation (2da edición), USA: Thomson Course Technology, ISBN 0-534-95097-3 • Garey, Michael R.; Johnson, David S., (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-71671045-5. • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. & Stein, Clifford (2010), Introduction to Algorithms (3ra edición), Cambridge, MA: MIT Press and McGraw-Hill, ISBN 0-262-03384-4.

Capítulo 2

NP-completo En teoría de la complejidad computacional, la clase de complejidad NP-completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP-completo. Se puede decir que los problemas de NPcompleto son los problemas más difíciles de NP y muy probablemente no formen parte de la clase de complejidad P. La razón es que de tenerse una solución polinómica para un problema NP-completo, todos los problemas de NP tendrían también una solución en tiempo polinómico. Si se demostrase que un problema NP-completo, llamémoslo A, no se pudiese resolver en tiempo polinómico, el resto de los problemas NP-completos tampoco se podrían resolver en tiempo polinómico. Esto se debe a que si uno de los problemas NP-completos distintos de A, digamos X, se pudiese resolver en tiempo polinómico, entonces A se podría resolver en tiempo polinómico, por definición de NP-completo. Ahora, pueden existir problemas en NP y que no sean NP-completos para los cuales exista solución polinómica, aun no existiendo solución para A.

Una transformación polinómica de L en C es un algoritmo determinista que transforma instancias de l ∈ L en instancias de c ∈ C, tales que la respuesta a c es positiva si y sólo si la respuesta a l lo es. Como consecuencia de esta definición, de tenerse un algoritmo en P para C, se tendría una solución en P para todos los problemas de NP. Esta definición fue propuesta por Stephen Cook en 1971. Al principio parecía sorprendente que existieran problemas NP-completos, pero Cook demostró (teorema de Cook) que el problema de satisfacibilidad booleana es NP-completo. Desde entonces se ha demostrado que miles de otros problemas pertenecen a esta clase, casi siempre por reducción a partir de otros problemas para los que ya se había demostrado su pertenencia a NP-completo; muchos de esos problemas aparecen en el libro de Garey and Johnson’s de 1979 Computers and Intractability: A Guide to NP-completeness.

Un problema que satisface la segunda condición pertenece a la clase NP-hard independientemente de que satisfaga la primera. Como ejemplo de un problema NP-completo encontramos el problema de la suma de subconjuntos que se puede enunciar como sigue: dado un conjunto S de enteros, ¿existe un subconjunto no vacío de S cuyos elementos 2.2 Historia sumen cero? Es fácil verificar si una respuesta es correcta, pero no se conoce mejor solución que explorar todos El concepto de “NP-completo” fue introducido por los 2n −1 subconjuntos posibles hasta encontrar uno que Stephen Cook en un artículo titulado 'The complexity cumpla con la condición. of theorem-proving procedures’ en las páginas 151-158 de Proceedings of the 3rd Annual ACM Symposium on Theory of Computing en 1971, aunque el término “NPcompleto” como tal no aparece en el documento. En la 2.1 Definición de NP-completo conferencia de ciencias de la computación hubo un intenso debate entre los científicos de la computación soUn problema de decisión C es NP-completo si: bre si los problemas NP-completos podían ser resueltos en tiempo polinómico o en una máquina de Turing deter1. C es un problema NP, y minista. John Hopcroft llevó a todos los asistentes de la conferencia a consenso concluyendo que el estudio sobre 2. Todo problema de NP se puede transformar polinó- si los problemas NP-completos son resolubles en tiempo micamente en C. polinómico debiera ser pospuesto ya que nadie había conseguido probar formalmente sus hipótesis ni en un sentiSe puede demostrar que C es NP demostrando que un do ni en otro. Esto se conoce como el problema ¿P=NP?. candidato a solución de C puede ser verificado en tiempo Nadie ha sido capaz aún de dar una respuesta final a este polinómico. problema, haciéndolo uno de los grandes problemas no 6

2.4. SOLUCIONES APROXIMADAS resueltos de la matemática. El Clay Mathematics Institute está ofreciendo una recompensa de un millón de dólares a quien logre dar una demostración de que P=NP o P≠NP. El Teorema de Cook demuestra que el problema de satisfacibilidad booleana es un problema NP-completo. En 1972, Richard Karp demostró que otros problemas eran también NP-completos (ver Lista de 21 problemas NPcompletos de Karp). A partir de los resultados originales del Teorema de Cook, cientos de problemas se han descubierto que pertenecen también a NP-completo por reducciones desde otros problemas que previamente se habían demostrado NP-completos, muchos de estos problemas han sido recogidos en libro de 1979 de Garey and Johnson’s Computers and Intractability: A Guide to NPCompleteness.

2.3 Ejemplos

7

Circuit - SAT

SAT

3-CNF SAT Clique Problem

Subset Problem

Vertex Cover Problem Hamiltonian Cycle

Travelling Salesman

Un problema interesante en teoría de grafos es el de Algunos problemas NP-completos, indicando las reducciones isomorfismo de grafos: Dos grafos son isomorfos si se usadas típicamente de completitud NP puede transformar uno en el otro simplemente renombrando los vértices. De los dos problemas siguientes: completitud NP. En este diagrama, una flecha de un problema a otro indica la dirección de la reducción. Nótese Isomorfismo de grafos: ¿Es el grafo G1 isomorque este diagrama puede resultar engañoso al llevarnos a fo al grafo G2 ? pensar que muestra una descripción de la relación mateIsomorfismo de subgrafos: ¿Es el grafo G1 isomática entre esos problemas, ya que existe una relación morfo a un subgrafo del grafo G2 ? de reducción de tiempo polinómico entre dos problemas NP-completos cualesquiera; pero esto indica que demosSe sospecha que el problema de isomorfismo de grafos trar estas reducciones de tiempo polinómicas ha sido más no está ni en P ni en NP-completo, aunque está en NP. fácil. Se trata de un problema difícil, pero no tanto como para A menudo hay solo una pequeña diferencia entre un proestar en NP-completo. blema P y uno NP-completo. Por ejemplo, el probleLa forma más sencilla de demostrar que un nuevo pro- ma 3SAT, una restricción del problema de satisfacibiliblema es NP-completo es primero demostrar que está en dad, sigue siendo NP-completo, mientras que el probleNP y luego transformar en tiempo polinómico un proble- ma 2SAT -ligeramente más estricto- está en P (especíma que ya esté en NP-completo a éste. Para ello resulta ficamente, NL-completo), y el problema MAX 2SAT útil conocer algunos de los problemas para los que exis- ligeramente más general- es, de nuevo, NP-completo. Dete prueba de pertenencia a NP-completo. Algunos de los terminar si un grafo puede ser coloreado con 2 colores, más famosos son: está en P, pero con tres colores es NP-completo, incluso cuando se restringe a los grafos planos. Determinar • Problema de satisfacibilidad booleana (SAT) si un grafo es ciclo o es bipartito es muy fácil (en L, pero encontrar un subgrafo máximo bipartito o ciclo es • Problema de la mochila (knapsack) NP-completo. Una solución del problema de la mochila (knapsack)dentro de de cualquier porcentaje fijo de la so• Problema del ciclo hamiltoniano lución óptima puede ser computado en tiempo polinómi• Problema del vendedor viajero co, pero encontrar la solución óptima es NP-completo. • Problema de la clique Véase también: • Categoría:Problemas NP-completos

2.4 Soluciones aproximadas

Actualmente, todos los algoritmos conocidos para problemas NP-completos utilizan tiempo exponencial con resA la derecha, un diagrama de algunos de los problemas pecto al tamaño de la entrada. Se desconoce si hay algority sus reducciones típicamente usadas para demostrar su mos más rápidos, por lo cual, para resolver un problema

8

CAPÍTULO 2. NP-COMPLETO

NP-completo de tamaño arbitrario, se utiliza uno de los que este tiene la restricción de que el programa solamente siguientes enfoques: puede llamar una vez al subalgoritmo y el valor retornado por este debe ser el valor de retorno del programa. • Aproximación: Un algoritmo que rápidamente encuentra una solución no necesariamente óptima, pero dentro de un cierto rango de error. En algunos casos, encontrar una buena aproximación es suficiente para resolver el problema, pero no todos los problemas NP-completos tienen algoritmos de aproximación. • Probabilístico: Un algoritmo probabilístico utiliza aleatoriedad para obtener en promedio una buena solución al problema planteado con una pequeña probabilidad de fallar, para una distribución de los datos de entrada dada. • Restricciones: Restringiendo la estructura de las entradas se pueden encontrar algoritmos más rápidos. • Casos particulares: Puede ocurrir que se reconozcan casos particulares del problema para los cuales existen soluciones rápidas. • Algoritmo genético: Algoritmos que mejoran las posibles soluciones hasta encontrar una que posiblemente esté cerca del óptimo. Tampoco existe forma de garantizar la calidad de la respuesta. • Heurísticas: Un algoritmo que trabaja razonablemente bien en muchos casos. En general son rápidos, pero no existe medida de la calidad de la respuesta. Las aproximaciones metaheurísticas suelen ser empleadas. Un ejemplo de algoritmo heurístico de complejidad O(n log n) es el algoritmo voraz utilizado para la coloración de vértices en algunos compiladores. Gracias a que la mayoría de máquinas RISC tienen un gran número de registros de propósito general, incluso una aproximación heurística es efectiva para esta aplicación.

2.5 Completitud bajo diferentes tipos de reducción En la definición de NP-completo dada anteriormente, el término “reducción” fue utilizado en el sentido transformar las instancias de un problema en instancias de otro (reducciones many-one). Otro tipo de reducción consiste en la “reducción en tiempo polinómico de Turing”. Un problema X es reducible en tiempo polinómico de Turing Y si dada una función que resuelve Y en tiempo polinómico, podría escribirse un programa que llamando a la subrutina anterior resuelva X en tiempo polinómico. Esto contrasta con el uso del término reducción del que hablábamos al principio ya

Si se definen el análogo a NP-completo con reducciones de Turing en lugar de reducciones many-one, el conjunto de problemas resultante no sería menor de NP-completo, de hecho se cuestiona si serían más grandes. Si los dos conceptos fuesen lo mismo, se seguiría que NO = CoNP. Esto se mantiene porque por definición las clases de los problemas NP-completos y co-NP-completos bajo las reducciones de Turing son las mismas gracias a que las clases definidas con reducciones many-one son subclases de estas mismas. Por lo tanto si ambas definiciones de la NP-completitud son iguales hay un problema co-NPcompleto (bajo ambas definiciones) como por ejemplo el complementario del problema de la satisfacibilidad booleana que es también NP-completo (bajo ambas definiciones). Esto implica que NP = co-NP como se muestra como prueba en el artículo sobre co-NP. Aunque la cuestión de si NP = co-NP es una pregunta abierta se considera muy poco probable porque también es muy poco probable que las dos definiciones de NP-completitud sean equivalentes. Otro tipo de reducción es empleado frecuentemente para definir NP-completitud es la de reducción de espacio logarítmico many-one que puede ser computerizada empleando únicamente una cantidad logarítmica de espacio. Ya que cada computación que puede ser realizada en espacio logarítmico también puede ser realizada en tiempo polinomial se razona que si hay una reducción de espacio logarítmico many-one también hay una reducción de tiempo polinómico many-one. Este tipo de reducción es más refinada que la más usual reducción de tiempo polinómico many-one y permite distinguir más clases como la P-completa. Ya sea en virtud de estos tipos de reducciones los cambios en la definición de NP-completo son todavía un problema abierto.

2.6 Véase también • P (clase de complejidad) • NP (clase de complejidad) • NP-complejo

2.7 Referencias • Garey, M. and D. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, 1979. ISBN 0-7167-1045-5 (Este es un libro clásico que desarrolla la teoría y clasifica muchos de los problemas NP-completos) • S. A. Cook, The complexity of theorem proving procedures, Proceedings, Third Annual ACM Sym-

2.7. REFERENCIAS posium on the Theory of Computing, ACM, New York, 1971, 151-158 • Complejidad computacional de juegos y rompecabezas • Tetris es difícil, aun para aproximarlo • ¡Buscaminas es NP-completo! • Lista de problemas NP-completo

9

Capítulo 3

Problema de decisión En teoría de la computación, un problema es un conjun• Las frases que describen una máquina de Turing y to de frases de longitud finita que tienen asociadas frases una cinta de entrada para esta máquina tal que la resultantes también de longitud finita. Un problema de máquina se para en un tiempo finito al procesar esa decisión es un problema en donde las respuestas posibles entrada. son «sí» o «no». Un ejemplo típico de problema de decisión es la pregunta: ¿Es un número entero dado primo? Los problemas de decisión son interesantes dado que toUna instancia de este problema sería: ¿Es 17 primo? dos los problemas formales (que incluye tanto lógicos coUn problema de decisión también se puede formalizar co- mo matemáticos) pueden ser redactados para que tomen mo el problema de decidir si una cierta frase pertenece a la forma de un problema de decisión. Las soluciones al un conjunto dado de frases, también llamado lenguaje for- problema de decisión y al problema original se diferenmal. El conjunto contiene exactamente las frases para las cian a lo sumo por un factor lineal. cuales la respuesta a la pregunta es positiva. La pregunta anterior sobre los números primos se puede ver también como el lenguaje de todas las frases en el alfabeto {0, 3.2 Véase también 1,..., 9} tales que el entero correspondiente es primo. Si existe un algoritmo que pueda decidir para cada posible frase de entrada si esa frase pertenece al lenguaje, entonces se dice que el problema es decidible, de otra forma se dice que es un problema indecidible. Cuando existe un algoritmo que puede responder positivamente cuando la frase está en el lenguaje, pero que corre indefinidamente cuando la frase no pertenece al lenguaje se dice que el problema es parcialmente decidible. En Teoría de la computabilidad, se estudia qué lenguajes son decidibles con diferentes tipos de máquinas. En teoría de la complejidad computacional se estudia cuántos recursos necesita un algoritmo decidible para ejecutar (recursos de tiempo, espacio, número de procesadores, tipo de máquina, etc.).

• Entscheidungsproblem

3.3 Referencias

3.1 Ejemplos Esos son algunos ejemplos de problemas de decisión expresados como lenguajes: • Las frases sobre el alfabeto {a, b} que contienen alternadas las letras a y b. • Las frases sobre el alfabeto {a, b, c} que contienen igual número de letras a y b. • Las frases que describen un grafo con aristas etiquetadas con números naturales que indican su longitud, dos vértices del grafo y un camino en el grafo que es el camino más corto entre esos dos vértices. 10

• Weisstein, Eric W. «(DecisionProblem) Definición». En Weisstein, Eric W. MathWorld (en inglés). Wolfram Research.

Capítulo 4

Optimización (cómputo) En cómputo, la optimización es el proceso de modificar un sistema para mejorar su eficiencia y el uso de los recursos disponibles (rendimiento). La optimización se puede llevar a cabo básicamente en tres niveles diferentes: • optimización de hardware • optimización de redes • optimización de software

11

Capítulo 5

Problema de la mochila $4

12

?

kg

15 kg $2

maño. Sin embargo, la estructura única del problema, y el hecho de que se presente como un subproblema de otros problemas más generales, lo convierten en un problema frecuente en la investigación. $2

g 2k

5.2 Definición

g 1k

$1

$10

g 1k

A continuación se define formalmente el problema.[3] Supongamos que tenemos n distintos tipos de ítems, que van del 1 al n. De cada tipo de ítem se tienen qi ítems disponibles, donde qi es un entero positivo que cumple 1 ≤ qi ≤ ∞ .

g 4k

Cada tipo de ítem i tiene un beneficio asociado dado por vi y un peso (o volumen) wi. Usualmente se asume que el beneficio y el peso no son negativos. Para simplificar la representación, se suele asumir que los ítems están listados en orden creciente según el peso (o volumen).

Ejemplo del problema de la mochila: dada una mochila con una capacidad de 15 kg que puedo llenar con cajas de distinto peso y valor, ¿qué cajas elijo de modo de maximizar mis ganancias y no exceder los 15 kg de peso permitidos?

En algoritmia, el problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo.

Por otro lado se tiene una mochila, donde se pueden introducir los ítems, que soporta un peso máximo (o volumen máximo) W. El problema consiste en meter en la mochila ítems de tal forma que se maximice el valor de los ítems que contiene y siempre que no se supere el peso máximo que puede soportar la misma. La solución al problema vendrá dado por la secuencia de variables x1 , x2 , ..., xn donde el valor de xi indica cuantas copias se meterán en la mochila del tipo de ítem i. El problema se puede expresar matemáticamente por medio del siguiente programa lineal:

5.1 Historia

∑n maximizar ∑i=1 vi xi n que tal i=1 wi xi ≤ W y 1 ≤ qi ≤ ∞.

El problema de la mochila es uno de los21 problemas NP-completos de Richard Karp, establecidos por el informático teórico en un famoso artículo de 1972.[1] Ha sido intensamente estudiado desde mediados del siglo XX Si q = 1 para i=1,2,...,n se dice que se trata del proi y se hace referencia a él en el año 1897, en un artículo de blema de la mochilla 0-1. Si uno o más q es infinito i George Mathews Ballard.[2] entonces se dice que se trata del problema de la moSi bien la formulación del problema es sencilla, su reso- chila no acotado también llamado a veces problema de lución es más compleja. Algunos algoritmos existentes la mochila entera. En otro caso se dice que se trata del pueden resolverlo en la práctica para casos de un gran ta- problema de la mochila acotado 12

5.4. MÉTODOS DE RESOLUCIÓN

13

5.3 Simplificaciones y generaliza- 5.4 Métodos de resolución ciones 5.3.1

Problema de la mochila simple

Este problema se ha resuelto tradicionalmente mediante programación lineal entera.

El hecho de que se trate de programación lineal hace reObservar que en un problema de la mochilla 0-1, si para ferencia a que la función a optimizar y las inecuaciones cada tipo de ítem el beneficio y los pesos son idénticos que constituyen las restricciones han de ser lineales, es de(vᵢ=wᵢ), entonces el problema quedaría formulado de la cir, han de ser funciones cuyas incógnitas estén elevadas exclusivamente a la unidad. siguiente forma Existe otra forma de resolver este tipo de problema, a través de los denominados algoritmos voraces. Una aproxi∑n maximizar ∑i=1 wi xi mación voraz consiste en que cada elemento a considerar n que tal se evalúa una única vez, siendo descartado o seleccionai=1 wi xi ≤ W y xi ∈ {0, 1}. do, de tal forma que si es seleccionado forma parte de ∑n la solución, y si es descartado, no forma parte de la soPor tanto si existe un vector xᵢ tal que i=1 wi xi = W lución ni volverá a ser considerado para la misma. Con , entonces esa será una solución al problema. Si existe este método no siempre es posible dar una solución a un una solución xᵢ de este tipo, resolver el problema de la problema. mochila realmente es resolver el problema de la suma de subconjuntos. Además si el conjunto de los pesos de los Otro sistema para resolver el problema de la mochila es elementos es una secuencia supercreciente, es decir, se mediante algoritmos genéticos que son métodos de optimización que tratan de hallar (xi,...,xn) tales que sea máverifica que: ximo.

wi >

i−1 ∑

wj

∀i

5.4.1 Algoritmos voraces

j=1

a) Aplicación del método: Entonces se dice que se trata de un problema de la mochila simple o también problema de la mochila tram- Partimos de la formulación del problema de la mochila posa. Este tipo de problemas tiene importantes aplicacio- aportada anteriormente: nes en el mundo de la criptografía. ∑n Maximizar i=1 bi xi a sujeto ∑n 5.3.2 Problema de la mochila de múltiple i=1 ci xi ≤ P elección xi ∈ {0, 1} con i = 1, . . . , n Si en un problema de la mochila 0-1 los ítems están subdivididos en k clases, denotadas por Nᵢ, y exactamente un ítem tienen que ser tomado de cada clase, entonces hablamos del problema de la mochila de múltiple elección.

La utilización de un algoritmo voraz consiste en introducir en la mochila según orden decreciente de utilidad (beneficio) los diversos objetos. En una primera etapa, se adicionarán unidades enteras hasta que, por motivo de capacidad, no sea posible seguir introduciendo enteros y haya que añadir la porción que quepa del siguiente objeto.

∑k ∑ maximizar vij xij b) Concepto de solución óptima: ∑ki=1 ∑j∈Ni que tal wij xij ≤ W, i=1 j∈N i ∑ Teorema: si se ordenan los objetos de forma de decrej∈Ni xij = 1 todo para 1 ≤ i ≤ k ciente en cuanto a su relación (utilidad/ponderación = y xij ∈ {0, 1} todo para 1 ≤ i ≤ k y j ∈ Ni . bi/ci) y se introducen en la mochila enteros en este or-

5.3.3

Problema de la mochila múltiple

den mientras quepan y cuando no quede capacidad para uno entero se añade la porción que aún tenga cabida el resultado al que se llega es una solución óptima.

Si en un problema de la mochila 0-1 tenemos n items y m mochilas con capacidades Wi entonces tenemos el pro5.4.2 blema de la mochila múltiple Un caso especial del problema de la mochila múltiple es cuando los beneficios son iguales a los pesos y todas las mochilas tienen la misma capacidad. Entonces se le llama problema de la múltiple suma de subconjuntos.

Algoritmos genéticos

Consisten en métodos adaptativos de optimización que tratan de hallar (xi,...,xn) tales que [Sumatoria (bi*xi) desde i= 1 hasta n] sea máximo. Pueden usarse para resolver problemas de búsqueda y optimización. Se basan en el

14

CAPÍTULO 5. PROBLEMA DE LA MOCHILA

proceso genético de los organismos vivos, por imitación de este proceso, los Algoritmos Genéticos son capaces de ir creando soluciones para problemas del mundo real. La evolución de dichas soluciones hacia valores óptimos del problema depende en buena medida de una adecuada codificación de las mismas. Para utilizar un algoritmo genético hacen falta tres elementos: Descripción de la población de individuos: cada individuo representa una solución factible a un problema dado. A cada individuo se le asigna un valor ó puntuación, relacionado con la bondad de dicha solución. Función de evaluación (llamada función de ajuste): encontrar una expresión matemática que puntúe a cada individuo de forma que nuestro ideal sea un máximo o un mínimo. Selección o Mecanismos de reproducción: la función de selección de padres más utilizada, es la denominada función de selección proporcional a la función objetivo, en la cual cada individuo tiene una probabilidad de ser seleccionado como padre que es proporcional al valor de su función objetivo, es decir, indica que cada objeto de la mochila tendrá una probabilidad de ser seleccionado que dependerá de la relación que exista entre beneficios y el peso que ocupa.

5.5 Referencias [1] Richard M. Karp (1972). «Reducibility Among Combinatorial Problems». En R. E. Miller y J. W. Thatcher (editores). Complexity of Computer Computations. Nueva York: Plenum. pp. 85–103. [2] G.B. Mathews, On the partition of numbers, Proceedings of the London Mathematical Society, 28:486-490, 1897. [3] Eric Gossett,"Discrete Mathematics with Proof”. Segunda edición. John Willey 2009.

Capítulo 6

Problema de la mochila simple El problema de la mochila simple, también llamado suma y por tanto en la posición correspondienproblema de la mochila supercreciente, es un tipo de te del vector solución xi habrá un 0. En caso problema de la mochila (problema NP-completo) al que contrario tendrá un 1 y se continuará la resolule aplican una serie de condiciones que hacen que pueda ción con los restantes elementos de la mochila ser planteado como un problema de la suma de subconpara el problema T-S juntos (problema NP-completo) que, si tiene solución, esta será única. Para este tipo de problemas, en el caso de que exista la Este tipo de problemas tiene importantes aplicaciones en solución, esta será única. el mundo de la criptografía

6.3 Aplicaciones

6.1 Definición

6.3.1 Clave simétrica Dados: • Un conjunto de m números enteros positivos S={S1 , S2 , ..., S }, ordenados de menor a mayor, donde la secuencia de los elementos cumplen la condición de que el elemento i-ésimo es mayor que la suma de los anteriores elementos (es una secuencia supercreciente). Matemáticamente

wi >

i−1 ∑

wj

Un problema de la mochila simple puede usarse como clave secreta de una algoritmo de cifrado simétrico. Para ello lo que hay que hacer es representar la información que se quiera cifrar en binario y se pasa cada bit por la mochila por la secuencia de números del conjunto S. Si un bit es 1 entonces se incluye en la suma el elemento que le corresponde. Si es un 0 entonces no se incluye. Por ejemplo sea S = {2, 4, 10, 19, 40}. Por tanto m = 5. Supongamos que quiero cifrar el mensaje M = ADIOS. Pasando el mensaje a ASCII/ANSI( A = 01000001, D = 01000100, I = 01001001, O = 01001111, S = 01010011) tenemos el mensaje (agrupo de 5 en 5 ya que m=5)

∀i

j=1

• Un valor T que es el resultado de alguna de las posibles sumas de esos elementos,

M = 01000 00101 00010 00100 10010 10011 11010 10011

Se debe encontrar S'={Sₐ, S , ..., S }, siendo S' el subcon- Haciendo las sumas de cada quinteto obtengo junto de S cuya suma sea igual al valor T. C = (4), (10+40), (19), (10), (2+19), (2+19+40), (2+4+19), (2+19+40)= 4, 50, 19, 10, 21, 61, 25, 61 6.2 Resolución La solución a este tipo de mochila es muy fácil debido a Que será el mensaje cifrado. que la secuencia S es una secuencia supercreciente: Para descifrar es receptor, que conoce S, recibe el mensaje C y opera de forma contraria resolviendo el problema de la mochila simple para cada uno de los valores de C. Se recorren los elementos de la mochila de mayor a menor comprobando si dicho valor es menor que T. Si es mayor, ese valor no estará en la

• Para obtener como suma un 4 la solución es 01000 15

16

CAPÍTULO 6. PROBLEMA DE LA MOCHILA SIMPLE

• 50 -> 00101 • 19 -> 00010 • 10 -> 00100 • 21 -> 10010 • 61 -> 10011 • 25 -> 11010 • 61 -> 10011 Si uno todos los bits y agrupo en grupos de 8 bits (ANSI/ASCII) obtengo el mensaje original. Esta forma de cifrar no es segura ya que es evidente que teniendo un suficientes pares, de mensaje originale y mensaje cifrado asociado, será muy fácil obtener la clave S con la que se está cifrando. Sin embargo esta forma de cifrar es muy rápida y puede será aprovechada en las aplicaciones de cifrado con clave asimétrica.

6.3.2

Clave asimétrica

La idea básica para usar una mochila simple en un sistema de criptografía asimétrica es conseguir una transformación secreta que transforme la mochila simple en una mochila general cuya resolución tenga un coste computacional alto. A esta mochila la llamaremos mochila tramposa. La clave pública será la mochila tramposa y con ella el emisor cifrará el mensaje de la misma forma que se hacía antes. La clave privada estará formada por los parámetros que permiten convertir el mensaje cifrado con la mochila tramposa en un mensaje cifrado con la mochila simple. Una vez obtenido esto el receptor puede descifrar el mensaje fácilmente usando la mochila simple. En resumen, el esquema se basa en cifrar con una función unidireccional basada en un problema NP-completo (el problema de la mochila) que tienen una puerta trampa que aprovecha el receptor para descifrar el mensaje. Si no se dispone de esa puerta trampa, el proceso de descifrado, al ser un problema NP-completo, teóricamente tendría un coste computacional muy alto. En esta idea se basa por ejemplo El criptosistema de Merkle-Hellman. Este algoritmo para hacer la transformción halla: ∑n • Un valor u tal que u > i=1 Si donde S1 , ..., Sn son los elementos de la mochila simple. • Un valor w entero tal que mcd(u, w) = 1 (aseguramos la existencia de w−1 en el grupo de los enteros de módulo u La mochila tramposa se halla usando la expresión Si′ = wSi (mod u) . Hay que verificar que la mochila

tramposa así obtenida no sea una mochila fácil de resolver (no siempre es así). Para descifrar el criptograma hay que aplicar w−1 C (mod u) para cada una de las sumas C obtenidas al cifrar. A continuación cada valor suma transformado hay que descifrarlo de la forma habitual con la mochila simple original, lo cual es trivial.

6.4 Bibliografía • Jorge Ramió Aguirre,"Aplicaciones criptográficas: libro guía de la asignatura seguridad informática”. Universidad Politécnica, Escuela Universitaria de Informática. Enero 1998.

6.5. TEXTO E IMÁGENES DE ORIGEN, COLABORADORES Y LICENCIAS

17

6.5 Texto e imágenes de origen, colaboradores y licencias 6.5.1

Texto

• Teoría de la complejidad computacional Fuente: https://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_complejidad_computacional? oldid=81462101 Colaboradores: Moriel, Robbot, Surscrd, Ascánder, Sms, Tano4595, Barcex, Ivan.Romero, Zild, AlfonsoERomero, Cesarsorm, Focojoaco, Chlewbot, Fer31416, Jstitch, BOTpolicia, CEM-bot, -jem-, Alexav8, Nicolasdiaz, Davius, Clecio Diehl, Pablohe, Bot que revierte, RoyFocker, JAnDbot, Maxidigital, TXiKiBoT, Bot-Schafter, Rei-bot, Uruk, AchedDamiman, AlnoktaBOT, Technopat, Elabra sanchez, SieBot, PaintBot, Loveless, Macarrones, Macarse, Naki~eswiki, Gato ocioso, DragonBot, Farisori, Estirabot, Azevedo bandeira, Alexbot, Juan Mayordomo, SilvonenBot, AVBOT, MastiBot, MarcoAurelio, LuqueII, SpBot, Argentumm, Nallimbot, Ptbotgourou, Martin78B, Xqbot, TobeBot, Halfdrag, RedBot, EmausBot, Grillitus, Ruben.mg, MerlIwBot, MetroBot, Allan Aguilar, JYBot, V.mendiola, Addbot, Miguelcldn y Anónimos: 51 • NP-completo Fuente: https://es.wikipedia.org/wiki/NP-completo?oldid=83017201 Colaboradores: Sabbut, Pablo.cl, Lourdes Cardenal, Riviera, Dodo, Ascánder, Sms, AlfonsoERomero, Rembiapo pohyiete (bot), Genba, RobotQuistnix, Chobot, BOT-Superzerocool, Cesarsorm, YurikBot, KnightRider, Tessier, CEM-bot, Chuffo, Davius, Thijs!bot, RoyFocker, Botones, JAnDbot, TXiKiBoT, Kevinkuja, Elopio, Rei-bot, Pólux, AlnoktaBOT, Cinevoro, YonaBot, SieBot, PaintBot, Macarse, Gato ocioso, Farisori, Estirabot, LordT, Alexbot, Ravave, AVBOT, Adelpine, Ginosbot, Diegusjaimes, CarsracBot, Adaumaholding, Macro.masek, Luckas-bot, MystBot, Nallimbot, ArthurBot, Jose.antonio.sa, SamuraiBot~eswiki, Rubpe19, Latacita, Addbot y Anónimos: 19 • Problema de decisión Fuente: https://es.wikipedia.org/wiki/Problema_de_decisi%C3%B3n?oldid=75013768 Colaboradores: Julie, Cek~eswiki, Ascánder, Trylks, Guille.hoardings, Chobot, GermanX, Tomatejc, Marsa, Botones, Netito777, Muro Bot, PaintBot, Farisori, Eduardosalg, Botito777, Lluvia, Mariana de El Mondongo, MerlIwBot, KLBot2, Acratta, Ineditable y Anónimos: 5 • Optimización (cómputo) Fuente: https://es.wikipedia.org/wiki/Optimizaci%C3%B3n_(c%C3%B3mputo)?oldid=81478548 Colaboradores: Cinabrium, Toxickore, Maleiva, Lobillo, Tab3r, Dhidalgo, Elabra sanchez, Muro Bot, PaintBot, Correogsk, Hoenheim, Waeswaes y Legobot • Problema de la mochila Fuente: https://es.wikipedia.org/wiki/Problema_de_la_mochila?oldid=79640481 Colaboradores: Jynus, Airunp, Chobot, GermanX, Fercufer, 333, Rosarinagazo, Dgilperez, Gsrdzl, AlleborgoBot, Muro Bot, SieBot, Loveless, BOTarate, Lauraamm, OboeCrack, Farisori, Botito777, AVBOT, Madalberta, Amirobot, Nallimbot, ArthurBot, Xqbot, SassoBot, PatruBOT, Dinamik-bot, Nachosan, Miss Manzana, HaŋaRoa, Tuc negre, Grillitus, KLBot2, MetroBot y Anónimos: 24 • Problema de la mochila simple Fuente: https://es.wikipedia.org/wiki/Problema_de_la_mochila_simple?oldid=71190039 Colaboradores: Fercufer y Turing92

6.5.2

Imágenes

• Archivo:Commons-emblem-disambig-notice.svg Fuente: Commons-emblem-disambig-notice.svg Licencia: GPL Colaboradores:

https://.wikimedia.org/wikipedia/commons/5/58/

• Commons-emblem-notice.svg Artista original: GNOME icon artists, Fitoschido • Archivo:Commons-emblem-question_book_yellow.svg Fuente: https://.wikimedia.org/wikipedia/commons/d/dd/ Commons-emblem-question_book_yellow.svg Licencia: CC BY-SA 3.0 Colaboradores: + Artista original: GNOME icon artists, Linfocito B • Archivo:Knapsack.svg Fuente: https://.wikimedia.org/wikipedia/commons/f/fd/Knapsack.svg Licencia: CC BY-SA 2.5 Colaboradores: ? Artista original: ? • Archivo:Relative_NPC_chart.svg Fuente: https://.wikimedia.org/wikipedia/commons/8/89/Relative_NPC_chart.svg Licencia: Public domain Colaboradores: Trabajo propio Artista original: Gian Luca RuggeroActam • Archivo:Spanish_Language_Wiki.svg Fuente: https://.wikimedia.org/wikipedia/commons/2/2a/Spanish_Language_Wiki.svg Licencia: CC BY-SA 3.0 Colaboradores: Derived from Wiki puzzle.svg by :Kimbar Artista original: James.mcd.nz

6.5.3

Licencia de contenido

• Creative Commons Attribution-Share Alike 3.0