Problema NP1
Publicado por Señor indecible (2 intervenciones) el 23/05/2006 12:11:42
Hola!
Hola, un amigo me ha pasado una serie de problemas pero no veo como se pueden resolver, son cuetiones a partir de un enunciado, creo que son sencillas pero a mi me trae de cabeza desde hace unos días!
A ver que os parece:
Sean los problemas SAT i CV, donde CV es el problema CIRCUIT-VALUE es P-completo, i EXPO que es un problema EXP-completo. ¿Cuales de las siguientes afirmaciones son ciertas i cuales falsas, i cuales dependerán de si P = NP?
a) HAMILTON < SAT i SAT < HAMILTON
b) sI P = NP entonces EXPO es NP
c) si SAT pertenece a P entonces CV es NP completo.
d) Como que todo problema P se puede expressar como un problema NP, entonces SAT<CV
Eso es todo! ;)
Hola, un amigo me ha pasado una serie de problemas pero no veo como se pueden resolver, son cuetiones a partir de un enunciado, creo que son sencillas pero a mi me trae de cabeza desde hace unos días!
A ver que os parece:
Sean los problemas SAT i CV, donde CV es el problema CIRCUIT-VALUE es P-completo, i EXPO que es un problema EXP-completo. ¿Cuales de las siguientes afirmaciones son ciertas i cuales falsas, i cuales dependerán de si P = NP?
a) HAMILTON < SAT i SAT < HAMILTON
b) sI P = NP entonces EXPO es NP
c) si SAT pertenece a P entonces CV es NP completo.
d) Como que todo problema P se puede expressar como un problema NP, entonces SAT<CV
Eso es todo! ;)
Valora esta pregunta
0