Instancias

Instancias

Entrada     A     Salida

Para cada problema, hay varias instancias que son los datos particulares de entrada del problema.

Dificultad de instancias

• No todas las instancias son iguales en términos de dificultad de resolución.
• Por ejemplo, la Máquina Turing de incremento unitario toma una cantidad diferente de transiciones cuando está presentando con entradas diferentes.
• El tamaño de la entrada evidentemente afecta, pero también afecta su estructura.
• La teoría clásica de complejidad computacional se formula en términos del tamaño de la instancia.
• Tamaño de la instancia
• Para llegar a la comparabilidad, uno busca siempre calcular el tamaño de instancia en los mismos términos.
• La manera más confiable es convertir todo en binario y luego contarlos bits.
• La manera más fácil depende del problema, pero es típicamente natural y evidente.

Tamaño de la instancia

• Para llegar a comparabilidad, uno busca siempre calcular el tamaño de instancia en los mismos términos
• La manera más confiable es convertir todo en binario y luego contar los bits
• La manera más fácil depende del problema, pero es típicamente natural y evidente.