¿Por qué importa el tamaño de la entrada en la teoría de NP?

Question

Cuando mi profesor nos introdujo en los temas de N/NP, lo primero que mencionó es el tamaño de la entrada, que define como el número de bytes necesarios para describir y escribir la entrada de un problema en un archivo . ¿Podría alguien explicarme por qué el tamaño de la entrada es importante para estos temas? Gracias.

EDIT: Me preocupa por qué es importante esta forma de medir el tamaño, especialmente para este tema de P/NP. Mi profesor mencionó el tiempo de ejecución pseudopolinomial (del problema de la mochila) que es algo relevante para esta forma de contar el tamaño de la entrada. No estoy seguro de cómo está conectado a la imagen NP, sobre todo porque justo después de redefinir el tamaño de la entrada, pasó a los ejemplos de reducción y no hay mención del tamaño de la entrada desde entonces. Y en el caso de los problemas NP-duros, dado que no se conoce ninguna forma de resolverlos de forma eficiente, ¿por qué deberíamos preocuparnos por la entrada de todos modos?

Answer 1

Veamos un ejemplo sencillo:

Ordena los siguientes números en orden ascendente:

8
485
314
2
146

Ahora ordena los siguientes números en orden ascendente:

72
277
304
326
287
152
205
68
444
250
70
490
384
81
180
126
397
402
259
295

Estoy dispuesto a apostar que fuiste capaz de ordenar fácilmente la primera serie de números en tu cabeza, pero la segunda lista te lleva bastante más tiempo.

Bien, entonces la ordenación es realmente un problema en P, no sólo en NP. Una gran parte del estudio de la complejidad de los algoritmos consiste en determinar cómo se ve afectado el tiempo de resolución de un problema a medida que el tamaño de las entradas es cada vez mayor.

Answer 2

La respuesta simplista es que las clases de complejidad se definen en términos del tamaño de la entrada (por supuesto, hay otras formas, a través de la complejidad descriptiva y así sucesivamente, pero me limitaré a lo básico). Así que introducir el tamaño de la entrada es esencial para definir las clases.

Naturalmente, la pregunta es por qué definir estas cosas en función del tamaño de la entrada? El conjunto razón de ser para estas clases es calcular la cantidad de recursos que necesitamos gastar para resolver un problema. Quizá nos interese saber cuánto tiempo se necesita, o cuánto espacio, o algún otro recurso, pero sobre todo queremos saber qué es posible y cuánto nos va a costar. Como han dicho los otros comentarios y la respuesta, es bastante razonable esperar que dar una entrada mayor consumirá más del recurso que nos interesa. Además, es poco interesante ver cuánto tiempo/espacio/etc. se necesita para resolver una única instancia; lo que queremos es una clasificación que nos diga cuánto tenemos que gastar para resolver cualquier instancia posible, sin tener que probar y ver (imagínate comprobar cuánto se tarda en resolver una instancia especialmente difícil de un problema especialmente difícil y descubrir que se tardan 10 años, o peor, la vida del universo).

Así que, por supuesto, necesitamos alguna forma de relacionar la instancia con la cantidad de recursos necesarios para resolverla. La primera medida natural es el tamaño de la instancia: si me das una instancia más grande, se necesita más tiempo/espacio/etc.