Autor Tema: Analizando el problema del empaquetamiento.

0 Usuarios y 1 Visitante están viendo este tema.

03 Octubre, 2019, 10:40 am
Leído 763 veces

martiniano

  • Moderador Global
  • Mensajes: 1,285
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola chicos.

Tengo que demostrar que el problema del empaquetamiento es \( \mathcal{NP} \). El problema del empaquetamiento me lo han enunciado como sigue:

Se consideran \( n \) objetos de tamaños \( v_1,...,v_n \), cajas de tamaño \( V \) y un número \( k \). Nos planteamos si es posible empaquetar los objetos en \( k \) cajas sin romper los objetos ni exceder el tamaño de las cajas.

Diría que el problema en sí lo tengo ya resuelto, lo que pasa es que en el proceso de resolución me surgieron bastantes dudas. La primera, que en Wikipedia encontré esto.

No acabo de ver que se trate del mismo problema, pero el caso es que si lo fuese Wikipedia apenas justifica que se trata de un problema NP, me parece entender que dice que lo es claramente y ya está, pero yo no lo veo tan claramente... En general, con el tema este de calcular complejidades, me cuesta ver qué es necesario justificar y qué no es necesario justificar.

Posteriormente se me ocurrió generar de manera no determinista todas las \( k-\textrm{particiones} \) de un \( n-\textrm{conjunto} \), en este caso el conjunto de números \( \{v_1,...,v_n\} \), y luego comprobar en tiempo polinómico que la suma de los números de todos los subconjuntos que forman cada una de las particiones es menor que \( V \). Tuve problemas a la hora de encontrar un algoritmo que te generase todas esas particiones, por lo que aquí tengo otra duda en la que me iría bien que alguien me iluminase un poco, si fuese posible. Y la cosa no acaba aquí...

Después, buscando entre una colección que tengo de exámenes resueltos encontré uno en el que se genera de manera no determinista y supuestamente en tiempo polinómico las permutaciones de \( n \) elementos. En un principio, este algoritmo me sirve, ya que, para cada permutación, se pueden ir sumando los tamaños de los elementos según el orden en el que vayan apareciendo en la permutación y cuando la suma exceda el valor de \( V \) se pone el valor de la suma igual al tamaño del último elemento que se iba añadir. Cuando se han tenido en cuenta a todos los elementos, si la suma se ha puesto a 0 un número de veces menor o igual a \( k \) el algoritmo acepta. El caso es que no acabo de ver que el algoritmo para generar las permutaciones sea \( \mathcal{NP} \), aquí pongo un pseudo-código del algoritmo que he copiado de la colección de problemas que os digo:

Código: [Seleccionar]
programa genera_permutaciones(p,n)
   continua : vector
   primera_permutacion(p,n)
   mientras leer (continua)=1 hacer
      es_ultima(p,n)
      si leer (acepta)=1 entonces
         escribir(continua,0)
      si_no
         ramificar
            escribir(continua,0)
         con
             siguiente_permutacion(p,n)
         fin_ramificar
      fin_si
   fin_mientras
fin

El programa primera_permutacion(p,n), pone en el vector \( p \) los números de \( 1 \) a \( n \) en orden creciente, y es_ultima(p,n) comprueba que en el vector \( p \) estén todos los números de \( 1 \) a \( n \) en orden decreciente.

El problema lo tengo con el programa siguiente_permutacion(p,n), que supuestamente coloca en el vector \( p \) la siguiente permutación a la que \( p \) representa. El orden en el que la solución dice que opera siguiente_permutacion(p,n) es el siguiente, para \( n=4 \).

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
...

La solución del examen dice sobre dicho programa que "se trata de reordenar los valores de la permutación, por tanto es de orden \( \mathcal{P} \)". Aquí tampoco veo que sea tan inmediato justificar el que este programa trabaje en tiempo polinómico. Creo haber demostrado que sí que lo hace, pero he tenido que encontrar el algoritmo explícitamente y utilizar dentro de él un algoritmo de ordenación, el quicksort, que trabaja en \( O(n^2) \)

A modo de apunte, en Wikipedia he encontrado el algoritmo de Heap, que se supone que es el más rápido conocido para generar permutaciones y que las ordena de manera diferente.

Básicamente, lo que me gustaría es entender por qué es obvio, si es que lo es, que ciertos algoritmos (los que he expuesto, para empezar) son de la clase \( \mathcal{P} \).

Un saludo y muchas gracias de antemano por la ayuda.

03 Octubre, 2019, 11:40 am
Respuesta #1

geómetracat

  • Moderador Global
  • Mensajes: 1,905
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Tengo que demostrar que el problema del empaquetamiento es \( \mathcal{NP} \). El problema del empaquetamiento me lo han enunciado como sigue:

Se consideran \( n \) objetos de tamaños \( v_1,...,v_n \), cajas de tamaño \( V \) y un número \( k \). Nos planteamos si es posible empaquetar los objetos en \( k \) cajas sin romper los objetos ni exceder el tamaño de las cajas.

Diría que el problema en sí lo tengo ya resuelto, lo que pasa es que en el proceso de resolución me surgieron bastantes dudas. La primera, que en Wikipedia encontré esto.

No acabo de ver que se trate del mismo problema, pero el caso es que si lo fuese Wikipedia apenas justifica que se trata de un problema NP, me parece entender que dice que lo es claramente y ya está, pero yo no lo veo tan claramente... En general, con el tema este de calcular complejidades, me cuesta ver qué es necesario justificar y qué no es necesario justificar.

Para justificar que un problema es \( NP \) lo más habitual, y lo más sencillo casi siempre, es usar la caracterización de problemas \( NP \) como aquellos para los que existe un algoritmo \( M \) en tiempo polinomial de manera que la solución al problema con input \( x \) es afirmativa si y solo si existe un certificado de longitud polinomial \( u \) tal que \( M(x,u)=1 \). Es decir, intuitivamente, los problemas \( NP \) son aquellos en los que se puede verificar una solución en tiempo polinomial (aunque quizás no sea posible encontrarla en tiempo polinomial).

Con esta caracterización tanto tu problema como el de la Wikipedia son inmediatos. En tu caso, un certificado sería una partición de \( v_1, \dots, v_n \) en \( k \) conjuntos, y el algoritmo verificador simplemente comprueba que la suma de los elementos en cada conjunto de dicha partición es como mucho \( V \). Esto se puede hacer claramente en tiempo polinomial.

Citar
Posteriormente se me ocurrió generar de manera no determinista todas las \( k-\textrm{particiones} \) de un \( n-\textrm{conjunto} \), en este caso el conjunto de números \( \{v_1,...,v_n\} \), y luego comprobar en tiempo polinómico que la suma de los números de todos los subconjuntos que forman cada una de las particiones es menor que \( V \). Tuve problemas a la hora de encontrar un algoritmo que te generase todas esas particiones, por lo que aquí tengo otra duda en la que me iría bien que alguien me iluminase un poco, si fuese posible. Y la cosa no acaba aquí...

Tu idea es buena. La idea sería repartir los números \( v_1, \dots, v_n \) en \( k \) listas de manera no determinista (en un tiempo polinómico). Si en cada paso pudieras hacer una elección aleatoria de un número del \( 1 \) al \( k \), esto se haría en tiempo lineal: para cada número \( v_i \) eliges al azar un número del \( 1 \) al \( k \) y lo metes en la lista que toca. De esa manera está claro que generas todas las posibles particiones de manera no determinista.
Como en principio solamente puedes hacer elecciones al azar entre dos posibilidades, puedes simular la elección entre \( k \) posibilidades como una sucesión de elecciones de dos. Algo así como: para cada \( v_i \) elijo entre meterlo en la lista \( 1 \) o en otra; si he elegido otra, en el siguiente paso elijo entre meterlo en la \( 2 \) o en otra superior... y así hasta la lista \( k \). Con esto tardas, como mucho, tiempo \( k \) para seleccionar la lista que le toca a cada \( v_i \), y por tanto, tiempo \( kn \) en obtener todas las particiones posibles de manera no determinista.

Fíjate que de esta manera además obtienes exactamente las particiones, pues en cada lista los números aparecerán siempre ordenados de menor a mayor.

Citar
Después, buscando entre una colección que tengo de exámenes resueltos encontré uno en el que se genera de manera no determinista y supuestamente en tiempo polinómico las permutaciones de \( n \) elementos. En un principio, este algoritmo me sirve, ya que, para cada permutación, se pueden ir sumando los tamaños de los elementos según el orden en el que vayan apareciendo en la permutación y cuando la suma exceda el valor de \( V \) se pone el valor de la suma igual al tamaño del último elemento que se iba añadir. Cuando se han tenido en cuenta a todos los elementos, si la suma se ha puesto a 0 un número de veces menor o igual a \( k \) el algoritmo acepta. El caso es que no acabo de ver que el algoritmo para generar las permutaciones sea \( \mathcal{NP} \), aquí pongo un pseudo-código del algoritmo que he copiado de la colección de problemas que os digo:

Código: [Seleccionar]
programa genera_permutaciones(p,n)
   continua : vector
   primera_permutacion(p,n)
   mientras leer (continua)=1 hacer
      es_ultima(p,n)
      si leer (acepta)=1 entonces
         escribir(continua,0)
      si_no
         ramificar
            escribir(continua,0)
         con
             siguiente_permutacion(p,n)
         fin_ramificar
      fin_si
   fin_mientras
fin

El programa primera_permutacion(p,n), pone en el vector \( p \) los números de \( 1 \) a \( n \) en orden creciente, y es_ultima(p,n) comprueba que en el vector \( p \) estén todos los números de \( 1 \) a \( n \) en orden decreciente.

El problema lo tengo con el programa siguiente_permutacion(p,n), que supuestamente coloca en el vector \( p \) la siguiente permutación a la que \( p \) representa. El orden en el que la solución dice que opera siguiente_permutacion(p,n) es el siguiente, para \( n=4 \).

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
...

La solución del examen dice sobre dicho programa que "se trata de reordenar los valores de la permutación, por tanto es de orden \( \matcal{P} \)". Aquí tampoco veo que sea tan inmediato justificar el que este programa trabaje en tiempo polinómico. Creo haber demostrado que sí que lo hace, pero he tenido que encontrar el algoritmo explícitamente y utilizar dentro de él un algoritmo de ordenación, el quicksort, que trabaja en \( O(n^2) \)

A modo de apunte, en Wikipedia he encontrado el algoritmo de Heap, que se supone que es el más rápido conocido para generar permutaciones y que las ordena de manera diferente.

Básicamente, lo que me gustaría es entender por qué es obvio, si es que lo es, que ciertos algoritmos (los que he expuesto, para empezar) son de la clase \( \mathcal{P} \).

Si te soy sincero no entiendo nada. Si he entendido bien el pseudocódigo (es bastante posible que no), la idea es empezar con la permutación \( 12 \dots n \) y en cada paso elegir de manera no determinista entre, o bien parar con la permutación que ya tenemos, o bien continuar con la siguiente (en un cierto orden establecido de antemano en el conjunto de todas las permutaciones). Si es así, este algoritmo no puede funcionar en tiempo polinomial, porque en el peor de los casos (acepta la última permutación), tarda un tiempo \( O(n!) \).

Un algoritmo no determinista en tiempo polinomial sería usar una idea parecida a la que he puesto antes. Para cada posición, eliges de forma no determinista un número entre \( 1 \) y \( n \) (que se puede hacer con \( n \) elecciones entre dos opciones), con la restricción de que en cada paso no puedes usar ningún número que haya aparecido antes.

Espero que esto te sea de ayuda.

PD: Por cierto, solamente por curiosidad, ¿qué curso es este que estás haciendo?
La ecuación más bonita de las matemáticas: \( d^2=0 \)

03 Octubre, 2019, 03:01 pm
Respuesta #2

martiniano

  • Moderador Global
  • Mensajes: 1,285
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Antes de nada, geómetracat: Muchísimas gracias por tu ayuda, me es de gran utilidad. El curso que estoy haciendo es uno que se imparte en la universidad de aquí, la UIB. Es una asignatura que se llama Teoría de la computación, del segundo curso de la carrera de Ingeniería Informática. Me han pasado toda la teoría y todos los problemas de la asignatura en sí. También he conseguido bastantes exámenes de otros años. El curso lo firma Jairo Rocha, y está bastante bien. En general, me resulta sencillo seguirlo. Sólo es en este tema, el 4, en el que me he atascado un poco más de la cuenta. Pero bueno, a base de embestidas y con vuestra ayuda lo acabaré sacando.

Para justificar que un problema es \( NP \) lo más habitual, y lo más sencillo casi siempre, es usar la caracterización de problemas \( NP \) como aquellos para los que existe un algoritmo \( M \) en tiempo polinomial de manera que la solución al problema con input \( x \) es afirmativa si y solo si existe un certificado de longitud polinomial \( u \) tal que \( M(x,u)=1 \). Es decir, intuitivamente, los problemas \( NP \) son aquellos en los que se puede verificar una solución en tiempo polinomial (aunque quizás no sea posible encontrarla en tiempo polinomial).

Claro, sí... Esto, antes de empezar el curso, pensaba que lo tenía claro. Pero ahora no estoy seguro de que lo tuviese tan claro. Es posible que me haya líado yo solito últimamente. Luego te explico...

Con esta caracterización tanto tu problema como el de la Wikipedia son inmediatos. En tu caso, un certificado sería una partición de \( v_1, \dots, v_n \) en \( k \) conjuntos, y el algoritmo verificador simplemente comprueba que la suma de los elementos en cada conjunto de dicha partición es como mucho \( V \). Esto se puede hacer claramente en tiempo polinomial.

Bien, justo lo que me cuesta es lo que no has incluido hasta ahora y es que hace falta un algoritmo no determinista que trabaje en tiempo polinómico y que genere todas las particiones, ¿no es así? Un algoritmo como el que describes aquí abajo y que es lo que me faltaba a mí (pienso yo) para resolver el problema a partir de esta idea:

La idea sería repartir los números \( v_1, \dots, v_n \) en \( k \) listas de manera no determinista (en un tiempo polinómico). Si en cada paso pudieras hacer una elección aleatoria de un número del \( 1 \) al \( k \), esto se haría en tiempo lineal: para cada número \( v_i \) eliges al azar un número del \( 1 \) al \( k \) y lo metes en la lista que toca. De esa manera está claro que generas todas las posibles particiones de manera no determinista.
Como en principio solamente puedes hacer elecciones al azar entre dos posibilidades, puedes simular la elección entre \( k \) posibilidades como una sucesión de elecciones de dos. Algo así como: para cada \( v_i \) elijo entre meterlo en la lista \( 1 \) o en otra; si he elegido otra, en el siguiente paso elijo entre meterlo en la \( 2 \) o en otra superior... y así hasta la lista \( k \). Con esto tardas, como mucho, tiempo \( k \) para seleccionar la lista que le toca a cada \( v_i \), y por tanto, tiempo \( kn \) en obtener todas las particiones posibles de manera no determinista.

Sí, creo que lo he entendido. De todas maneras, estos días me lo miraré más despacio y si me queda alguna duda me volveré a pasar por este hilo.

Después, buscando entre una colección que tengo de exámenes resueltos encontré uno en el que se genera de manera no determinista y supuestamente en tiempo polinómico las permutaciones de \( n \) elementos. En un principio, este algoritmo me sirve, ya que, para cada permutación, se pueden ir sumando los tamaños de los elementos según el orden en el que vayan apareciendo en la permutación y cuando la suma exceda el valor de \( V \) se pone el valor de la suma igual al tamaño del último elemento que se iba añadir. Cuando se han tenido en cuenta a todos los elementos, si la suma se ha puesto a 0 un número de veces menor o igual a \( k \) el algoritmo acepta. El caso es que no acabo de ver que el algoritmo para generar las permutaciones sea \( \mathcal{NP} \), aquí pongo un pseudo-código del algoritmo que he copiado de la colección de problemas que os digo:

Código: [Seleccionar]
programa genera_permutaciones(p,n)
   continua : vector
   primera_permutacion(p,n)
   mientras leer (continua)=1 hacer
      es_ultima(p,n)
      si leer (acepta)=1 entonces
         escribir(continua,0)
      si_no
         ramificar
            escribir(continua,0)
         con
             siguiente_permutacion(p,n)
         fin_ramificar
      fin_si
   fin_mientras
fin

El programa primera_permutacion(p,n), pone en el vector \( p \) los números de \( 1 \) a \( n \) en orden creciente, y es_ultima(p,n) comprueba que en el vector \( p \) estén todos los números de \( 1 \) a \( n \) en orden decreciente.

El problema lo tengo con el programa siguiente_permutacion(p,n), que supuestamente coloca en el vector \( p \) la siguiente permutación a la que \( p \) representa. El orden en el que la solución dice que opera siguiente_permutacion(p,n) es el siguiente, para \( n=4 \).

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
...

La solución del examen dice sobre dicho programa que "se trata de reordenar los valores de la permutación, por tanto es de orden \( \matcal{P} \)". Aquí tampoco veo que sea tan inmediato justificar el que este programa trabaje en tiempo polinómico. Creo haber demostrado que sí que lo hace, pero he tenido que encontrar el algoritmo explícitamente y utilizar dentro de él un algoritmo de ordenación, el quicksort, que trabaja en \( O(n^2) \)

A modo de apunte, en Wikipedia he encontrado el algoritmo de Heap, que se supone que es el más rápido conocido para generar permutaciones y que las ordena de manera diferente.

Básicamente, lo que me gustaría es entender por qué es obvio, si es que lo es, que ciertos algoritmos (los que he expuesto, para empezar) son de la clase \( \mathcal{P} \).

Si te soy sincero no entiendo nada. Si he entendido bien el pseudocódigo (es bastante posible que no), la idea es empezar con la permutación \( 12 \dots n \) y en cada paso elegir de manera no determinista entre, o bien parar con la permutación que ya tenemos, o bien continuar con la siguiente (en un cierto orden establecido de antemano en el conjunto de todas las permutaciones). Si es así, este algoritmo no puede funcionar en tiempo polinomial, porque en el peor de los casos (acepta la última permutación), tarda un tiempo \( O(n!) \).

Pues a mí me parece que lo has entendido bastante bien. De hecho, tienes toda la razón en que este algoritmo para generar permutaciones no opera en tiempo polinómico. Vaya... Qué extraño... Yo pensaba que las soluciones que vienen en la colección de exámenes resueltos de la que hablo eran las oficiales. No me había detenido a analizar el algoritmo. En el examen del que lo he sacado utilizaba este algoritmo para construir otro, de clase \( \mathcal{NP} \) que permitiese resolver el problema del viajante.

Spoiler
Dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y vuelve a la ciudad de origen?
[cerrar]

Un algoritmo no determinista en tiempo polinomial sería usar una idea parecida a la que he puesto antes. Para cada posición, eliges de forma no determinista un número entre \( 1 \) y \( n \) (que se puede hacer con \( n \) elecciones entre dos opciones), con la restricción de que en cada paso no puedes usar ningún número que haya aparecido antes.

Sí claro, con este algoritmo parece que sí se generan todas las permutaciones en tiempo polinómico. Como ves, parece que encontrar estos algoritmos de generación es lo que más me cuesta. De todas maneras, ya te digo que analizaré los detalles de tu valiosísima respuesta con más tiempo estos días y si me quedase alguna duda te lo comentaría. Bueno, ¿y qué era lo que no entendías?  :D.

Muchas gracias por todo, de verdad. Y un saludo.

04 Octubre, 2019, 11:18 am
Respuesta #3

geómetracat

  • Moderador Global
  • Mensajes: 1,905
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Bien, justo lo que me cuesta es lo que no has incluido hasta ahora y es que hace falta un algoritmo no determinista que trabaje en tiempo polinómico y que genere todas las particiones, ¿no es así? Un algoritmo como el que describes aquí abajo y que es lo que me faltaba a mí (pienso yo) para resolver el problema a partir de esta idea:

(...)

No me queda muy claro si me has entendido bien o no, así que por si acaso lo repito intentándolo explicar de forma algo más clara.
Hay dos definiciones equivalentes de problema \( NP \). Sea \( L \) un lenguaje (pongamos en el alfabeto \( \{0,1\} \) por simplificar, aunque no es importante, puedes sustituir por cualquier alfabeto finito). Entonces \( L \) es \( NP \) si y solo si se cumple una cualquiera de las dos condiciones siguientes:
1) Existe un algoritmo no determinista \( M \) en tiempo polinómico tal que \( Mx = 1 \iff x \in L \).
2) Existe un algoritmo determinista \( N \) en tiempo polinómico y un polinomio \( p(t) \) tal que \( \exists u \in \{0,1\}^{p(|x|)} N(x,u)=1 \iff x \in L \).

En el caso 2) al \( u \) que cumple \( N(x,u)=1 \) se le llama certificado y la idea detrás es que \( u \) codifica una solución al problema con input \( x \) (certifica que \( x \in L \)).

Entonces, para ver que tu lenguaje está en \( NP \), basta con que pruebes una sola de las dos cosas. En la parte inicial de mi mensaje, te decía que probar 2) para tu problema es fácil: existe un "comprobador de soluciones" determinista en tiempo polinómico: si me dan un input \( x \) y una supuesta partición solución \( u \), compruebo que la suma de los elementos de cada conjunto de la partición sean a lo sumo \( V \); si es así acepto, si no rechazo.
De esta forma no hace falta buscar ningún algoritmo para generar particiones de forma no determinista ni nada por el estilo.

El resto del mensaje sí que iba dirigido a una solución usando la caracterización 1).

Citar
(...)
 Bueno, ¿y qué era lo que no entendías?  :D.

Pues lo que no me cuadraba es que has dicho que eso formaba parte de las soluciones a los exámenes, y tal como lo veo está mal. Por eso me resultaba extraño. No sé si se me escapa algo o directamente la supuesta solución está mal.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

04 Octubre, 2019, 04:46 pm
Respuesta #4

martiniano

  • Moderador Global
  • Mensajes: 1,285
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

No me queda muy claro si me has entendido bien o no, así que por si acaso lo repito intentándolo explicar de forma algo más clara.
Hay dos definiciones equivalentes de problema \( NP \). Sea \( L \) un lenguaje (pongamos en el alfabeto \( \{0,1\} \) por simplificar, aunque no es importante, puedes sustituir por cualquier alfabeto finito). Entonces \( L \) es \( NP \) si y solo si se cumple una cualquiera de las dos condiciones siguientes:
1) Existe un algoritmo no determinista \( M \) en tiempo polinómico tal que \( Mx = 1 \iff x \in L \).
2) Existe un algoritmo determinista \( N \) en tiempo polinómico y un polinomio \( p(t) \) tal que \( \exists u \in \{0,1\}^{p(|x|)} N(x,u)=1 \iff x \in L \).

En el caso 2) al \( u \) que cumple \( N(x,u)=1 \) se le llama certificado y la idea detrás es que \( u \) codifica una solución al problema con input \( x \) (certifica que \( x \in L \)).

Entonces, para ver que tu lenguaje está en \( NP \), basta con que pruebes una sola de las dos cosas. En la parte inicial de mi mensaje, te decía que probar 2) para tu problema es fácil: existe un "comprobador de soluciones" determinista en tiempo polinómico: si me dan un input \( x \) y una supuesta partición solución \( u \), compruebo que la suma de los elementos de cada conjunto de la partición sean a lo sumo \( V \); si es así acepto, si no rechazo.
De esta forma no hace falta buscar ningún algoritmo para generar particiones de forma no determinista ni nada por el estilo.

Ya lo entiendo ¡¡¡Claro!!! Ya tenía yo la sensación de estarme yendo por las ramas con estas cosas. Si es que además la clave ya me la habías dado en el mensaje de antes.

Para justificar que un problema es \( NP \) lo más habitual, y lo más sencillo casi siempre, es usar la caracterización de problemas \( NP \) como aquellos para los que existe un algoritmo \( M \) en tiempo polinomial de manera que la solución al problema con input \( x \) es afirmativa si y solo si existe un certificado de longitud polinomial \( u \) tal que \( M(x,u)=1 \). Es decir, intuitivamente, los problemas \( NP \) son aquellos en los que se puede verificar una solución en tiempo polinomial (aunque quizás no sea posible encontrarla en tiempo polinomial).

Ahora sí lo entiendo, lo que se me había escapado era que basta con que el certificado tenga longitud polinomial, no hace falta encontrar el algoritmo no determinista en sí. Mucha gracias. Comprendido  :aplauso:

Pues lo que no me cuadraba es que has dicho que eso formaba parte de las soluciones a los exámenes, y tal como lo veo está mal. Por eso me resultaba extraño. No sé si se me escapa algo o directamente la supuesta solución está mal.

Pues ya... pero lo que has dicho tiene todo el sentido, el algoritmo ese que genera permutaciones lo hace en un tiempo mayor a \( n! \), en el peor de los casos, por tanto no es polinómico. Intentaré contactar con el responsable de la asignatura para preguntarle, a ver si hay suerte...

Venga, muchísimas gracias por la ayuda. Un saludo.

17 Octubre, 2019, 07:23 am
Respuesta #5

martiniano

  • Moderador Global
  • Mensajes: 1,285
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

He expuesto al profe la crítica al algoritmo genera_permutaciones y ha estado de acuerdo.

Un saludo.