Complejidad Computacional

Question 1

Cuatro tipos de problemas fundamentales

Answer 1

• Búsqueda
• Decisión
• Evaluación
• Optimización

Question 2

Problema de decisión

Answer 2

Problemas con respuesta binaria

Question 3

Formalización de un problema de decisión

Answer 3

Determinar si una instancia de un lenguaje (I) se encuentra o no en un subconjunto (L) de ese lenguaje.

Question 4

Formalización de si un algoritmo resuelve un problema de decisión

Answer 4

Si es que responde SI para cada input cuando este pertenece al subconjunto y NO cuando este no pertenece al subconjunto.

Question 5

Meta-clase de complejidad de tiempo deterministica

Answer 5

DTIME(T(n))

Conjunto de problemas donde existe un alg. con complejidad O(T(n))

Question 6

Clase de complejidad polinomial

Answer 6

PTIME

la unión de DTIME(nᵏ) para todo k > 0

Question 7

Los problema en la clase PTIME suelen llamarse…

Answer 7

tratables (tractables)

Question 8

Definición de verificador para NP

Answer 8

Dada una instancia I de un problema Π, debe existir un certificado c(I) de tamaño polinomial con respecto a I tal que existe un algoritmo que usando c(I) puede verificar si la respuesta es SI o NO.

Question 9

¿Cómo probar que un problema X es NP-completo?

Answer 9

1. Probar que X está en NP
2. Reducir un problema conocido NP-completo Y a X

Question 10

Reducción

Answer 10

Encontrar un algoritmo de tiempo polinomial que puede mapear los inputs de un problema X de forma equivalente a un problema Y

Question 11

¿Cómo probar que un problema es NP?

Answer 11

• Encontrar un algoritmo polinomial deterministico que resuelva el problema
• Encontrar un certificado y un algoritmo verificador para verificar una solución al problema

Question 12

Si un algoritmo X es reducible a Y, esto significa que

Answer 12

Y es al menos tan díficil como X