El mundo abunda en afirmaciones como:
El problema del viajante de comercio es NP-completo.
Pero cuando intento seguir los enlaces de Internet "por la madriguera del conejo", no consigo una explicación verdaderamente sensata de lo que significan realmente este tipo de afirmaciones. Intentaré reducir esto exactamente a la parte en la que se produce el "agujero negro de la comprensión" para mí.
Por ejemplo, el problema del viajante de comercio. Cuando leo sobre esto, todo lo que veo es una función. Explícitamente, hay una función que mapea cada gráfico ponderado $G$ al conjunto de todos los ciclos hamiltonianos en $G$ de longitud mínima. También podríamos denotar esta función $\mathrm{TSF}$ y llamarlo función de vendedor ambulante.
Ahora cambiemos un poco de tema. Cuando sigo los enlaces relacionados con la completitud NP, consigo conjeturar que la completitud NP puede definirse formalmente como una colección de subconjuntos de $\mathbb{N}$ .
$$\mathrm{NPCOMP} \subseteq 2^\mathbb{N}$$
Con más detalle, supongo que
$$\mathrm{NPCOMP} = \mathrm{NP} \cap \mathrm{NPHARD}$$
Bien. Intentemos juntarlas. Por conveniencia, por un blurgle me refiero a una función que (como $\mathrm{TSF})$ asigna a cada gráfico ponderado $G$ un conjunto de ciclos en $G$ . Así que lo que sucede, presumiblemente, es que podemos asignar a cada burbuja $\mathrm{FOO}$ una colección correspondiente de subconjuntos de $\mathbb{N}$ Llama a esto $\underline{\mathrm{FOO}}$ . Por lo tanto, podemos definir que un borrón $\mathrm{FOO}$ es NP-completo si $\underline{\mathrm{FOO}} \subseteq \mathrm{NPCOMP}.$
Por lo tanto, ya que $\mathrm{TSF}$ es un borrón, podemos reinterpretar la declaración inicial como que $$\underline{\mathrm{TSF}} \subseteq \mathrm{NPCOMP}$$
Además, parece razonable definir que el problema del vendedor viajero es igual a $\underline{\mathrm{TSF}}.$
El problema que estoy teniendo (y este es el "agujero negro de la comprensión") es que no entiendo cómo llegar desde un blurgle $\mathrm{FOO}$ a $\underline{\mathrm{FOO}}$ que pretende ser una colección de subconjuntos de $\mathbb{N}$ . Por lo tanto, aunque puedo describir $\mathrm{TSF}$ en términos completamente precisos, no tengo ni idea de lo que $\underline{\mathrm{TSF}}$ es, excepto que es una colección de subconjuntos de $\mathbb{N}$ .
Pero es mucho peor que eso. Hablando en términos muy generales, y olvidando todo lo relacionado con la teoría de los grafos y los borrones y demás, y limitándose a tratar las cosas al mayor nivel de abstracción posible, parece que la gente suele tratar con un objeto $\mathrm{FOO}$ y luego comienzan a hablar de la "complejidad" del foo, lo que implícitamente significa que están estudiando $\underline{\mathrm{FOO}},$ pero parece que, en general, nadie te dice realmente cómo llegar desde $\mathrm{FOO}$ a $\underline{\mathrm{FOO}}.$
Entonces, mi pregunta es:
Pregunta. ¿Cómo se interpretan afirmaciones como: "El problema del viajante de comercio es NP-completo" cuando en realidad el escritor no te ha dado un problema en absoluto, lo que te ha dado es un objeto $\mathrm{FOO}$ (como la función del viajante de comercio), pero lo siguiente es que hacen afirmaciones sobre el problema correspondiente $\underline{\mathrm{FOO}}$ sin decir precisamente qué subconjuntos de $\mathbb{N}$ ¿a qué se refiere esto?
Supongo que sólo hay que hacer una conjetura: pero, si es así, ¿cómo se supone que debemos hacer esta conjetura, y por qué la conjetura del lector coincidiría con lo que el escritor está pensando realmente?
