P/NP: Reducciones Polinomiales, NP-Hard, NP-Complete, SAT Flashcards
Explique el concepto de transición de Problema de Optimización a Problema de Decisión
Dado un problema de optimización Q, podemos reformularlo como un problema de decisión y viceversa. Y así, encontrar la respuesta en tiempo polinómico o pseudopolinómico.
¿Cuándo se resuelve eficientemente un problema?
Un algoritmo A resuelve eficientemente un problema S si para toda instancia I de S, el algoritmo A encuentra solución en tiempo polinomial.
¿Qué es P?
Se conoce como P al conjunto de problemas de decisión para los que existe un algoritmo que lo resuelve en forma eficiente (polinómica).
¿Cuándo un algoritmo B certifica de forma eficiente un problema S?
Un algoritmo B certifica o verifica eficientemente un problema de decisión S si para toda instancia de ese problema, dado un certificado t, se puede verificar su solución en tiempo polinomial.
Explique el concepto de certificado
El certificado es el resultado de la combinación de valores de variables de un conjunto. Por ejemplo: X = {x1,x2,x3}.
Entonces, un certificado puede ser: {x1 = 1, x2 = 0, x3 = 0}, y se debe verificar que el resultado obtenido por ese certificado en el problema es true.
¿Qué es NP?
Se conoce como NP al conjunto de problemas de decisión para los que existe un algoritmo que lo certifique en forma eficiente (es decir, en tiempo polinomial).
Explique por qué P ⊆ NP
Si un problema Q pertenece a P, significa que existe un algoritmo que lo resuelve en tiempo polinomial.
Por lo tanto, si un problema Q tiene un algoritmo A que lo resuele en tiempo polinomial, significa que podemos definir a B como un algoritmo que certifica al problema Q y lo hace en tiempo polinomial.
B(I,t): solucion = A(I) return solucion == t
Explique por qué NP ⊈ P
Si el problema Q pertenece a NP, significa que existe un algoritmo B que lo certifica en tiempo polinomial.
- Si pudiésemos asegurar que la existencia de B garantiza la existencia de un algoritmo A que resuelve el problema Q en tiempo polinomial => P = NP
- De lo contrario, P != NP
Este es un problema sin resolver dentro de la ciencia de la computación.
Explique:
- ¿Qué se busca con las reducciones polinomiales?
- ¿Cuál es la idea?
- ¿Que significa reducir del problema Y al problema X?
Con las reducciones polinomiales buscamos clasificar problemas computacionales de acuerdo a la complejidad que requiere su resolución.
La idea es reducir un problema a otro conocido, para poder resolverlo.
Reducir del problema Y al problema X es tener un algoritmo de tiempo polinómico que convierta los inputs de Y en inputs equivalentes de X. Las reducciones dicen que si yo sé cómo resolver el problema X, entonces también sé cómo resolver el problema Y.
Además, si el algoritmo Y pertenece a P, entonces X pertenece a P; porque tienen inputs equivalentes. Esto también funciona para NP.
Esto quiere decir que si Y <=p X, X es al menos tan dificil como Y.
Explique el concepto de acotar un problema a la clase P, con sus 3 casos posibles para P
Sea X,Y problemas tal que:
- Caso 1
- X pertenece a P (se resuelve en tiempo polinomial)
- Y <=p X
Entonces Y pertenece a P, porque X es igual o más complicado que Y.
- Caso 2
- Y no pertenece a P
- Y <=p X
Entonces X tampoco pertenece a P.
- Caso 3
- Y <=p X
- X <=p Y
Entonces X e Y tienen la misma complejidad.
Explique la propiedad de transitividad
Sean X,Y,Z problemas tal que:
- Z <=p Y
- Y <=p X
Entonces Z <=p X. Además, si X pertenece a P, Z también pertenece.
¿Qué es NP-Hard?
Sean X,Y problemas tal que:
- Y pertenece a NP
- Y <=p X
Entonces X pertenece a NP-Hard. Es decir, X es al menos igual de difícil que cualquier problema en NP. O sea, X es igual o más difícil que cualquier problema de NP.
¿Qué es NP-Complete?
Sea X un problema tal que:
- X pertenece a NP
- X pertenece a NP-Hard
Entonces X pertenece a NP-C. Es decir, X es uno de los problemas más difíciles dentro de NP.
Explique el problema SAT
SAT: Problema de Satisfacibilidad Booleana
SAT es un problema que pertenece a NP-C.
El problema SAT consiste en determinar si dada una expresión booleana, existe una asignación de valores tales para que la expresión sea verdadera.
Supongamos que se nos da un set X de n variables booleanas {x1, ..., xn}, que pueden tener valor 0 o 1.
Queremos encontrar una asignación de valores para una cantidad de cláusulas (expresiones booleanas) tal que el resultado de todas las cláusulas sea 1 o true.
SAT: Explique por qué pertenece a NP
Sea I una instancia del problema SAT y t un certificado que corresponde a un valor de asignación de cada variable, podemos certificar en tiempo polinomial si esa asignación de variables produce un resultado true, reemplazando las variables en las cláusulas.
