¿Hay algún problema que sea la complejidad NP en el espacio [matemático] n [/ matemático] -D pero es la complejidad [matemático] O (1) [/ matemático] en el espacio [matemático] n + 1 [/ matemático] -D?

Hay un sentido en el que la respuesta es trivialmente “Sí”, y un sentido más significativo en el que la respuesta es “No”. Sin embargo, la respuesta real es que tienes algunos conceptos erróneos extraños sobre la complejidad.

Comencemos con tu ejemplo. El gusano y yo necesitaremos la misma cantidad de tiempo para resolver este problema asintóticamente, en el orden de la distancia desde el círculo hasta el primer cuadrado, suponiendo que la única operación que se nos permite a ambos es “mover 1 a la derecha y prueba si hay un cuadrado allí “. Si lo hago con mis ojos y si el gusano lo hace con todo su cuerpo es irrelevante.

Pero, ¿qué pasa si subimos una dimensión? Podemos actualizar la operación para “mover 1 en cualquier dirección”, pero aún así el problema se vuelve mucho más difícil tanto para mí como para el gusano, aunque todavía solo tengo que mover los ojos.

Lo que puede faltar aquí es la idea del comportamiento asintótico. El ejemplo ciertamente no lo captura.

Entonces volvamos a la pregunta general. Existe cierta ambigüedad en la idea de un problema que cambia las dimensiones. ¿Qué cambiamos cuando aumentamos la dimensión? ¿Estamos simplemente agregando grados de libertad y ajustando todas las operaciones permitidas para aprovechar potencialmente este nuevo grado de libertad?

Entonces sí, hacer esto podría hacer que un problema anteriormente difícil fuera trivial. De hecho, hay problemas que pueden tener o no soluciones en baja dimensión que siempre tienen una solución en alta dimensión, de modo que el algoritmo trivial “siempre genera ‘sí'” es un algoritmo O (1) calificado.

Por ejemplo, el problema “¿puede esta curva cerrada 1D transformarse en un círculo sin pasar a través de sí misma?” Es un problema de complejidad desconocida cuando se incrusta en el espacio 3D (el problema de anudamiento), pero trivial en el espacio 4D (no existen nudos por encima de 3 dimensiones )

Pero tenga en cuenta que solo hemos agregado un grado de libertad. Todavía estamos trabajando con una curva 1D.

Pero si permitimos que nuestros datos también tengan una dimensión más alta además del grado de libertad, generalmente el problema es al menos tan difícil (ya que el problema original también es una instancia del problema de dimensión más alta). Por lo general, es mucho más difícil. Por ejemplo, el género de nudos de 3 múltiples es un problema NP-completo conocido.

Entonces, básicamente, depende de lo que quieras decir. Hacer que cada parte de un problema sea de alta dimensión lo hace más difícil, mientras que solo agregar más grados de libertad podría hacerlo trivialmente fácil.

Las definiciones de P y NP no contienen la palabra “dimensionalidad”. Tiene en cuenta un conjunto de palabras de entrada. Pero si tratamos de dar sentido a la pregunta …

Si cierto problema no puede resolverse en [math] n [/ math] -dimensional space en tiempo polinomial (pero puede verificarse) y puede resolverse en tiempo polinomial en [math] n + 1 [/ math] -dimensional space, allí debe ser un conjunto de pruebas S para [math] n [/ math] -dimensional space. Pero ese espacio n-dimensional es una proyección de un espacio con una dimensión mayor, lo que hace que el cálculo de una prueba sea un problema con la complejidad polinómica. Prueba polinómica + verificación polinomial = complejidad polinomial en [math] n [/ math] -dimensional space, por lo tanto, no es NP “en [math] n [/ math] -dimensional space”, lo que sea que eso signifique.

Y el problema incluido en los detalles de la pregunta tampoco tiene sentido, pero Divyanth ya lo ha explicado.

No puedo evitar preguntarme si esta pregunta es una de esas tonterías pseudocientíficas que suenan profundamente y que hacen que las personas se vean inteligentes. Desde la perspectiva del gusano circular, viaja justo hasta que golpea lo primero. Lo primero que golpea, obviamente es el más cercano. Ahí vas; lo resolviste en O (1) tiempo. Si quieres la solución como algoritmo, esto es lo que escribiría

Paso 1: ve a la derecha.

Paso 2: Si (golpeo algo)

Paso 3: Identifica lo que golpeé

Paso 4: Dado que lo que golpeé es un cuadrado azul, el cuadrado azul está más cerca de mí.

Los algoritmos están destinados a resolver problemas de la manera más simple posible. Sin embargo, los conceptos que usa son como pedirle al increíble Hulk que abra un tarro de pepinillos.