¿El problema de N Queens es NP-duro?

El problema de N-queen es este:

Entrada: N

Salida: una colocación de N "reinas" en un tablero de ajedrez de NXN de modo que no haya dos reinas en la misma fila, columna o diagonal.

Al hacer una búsqueda en Google sobre esto, descubrí que muchas diapositivas de muchos profesores afirman que este es un problema NP-Hard (por ejemplo, web.mst.edu/~ercal/387/slides/NP-Hard.ppt)

Sin embargo, no he podido encontrar una prueba (o derivar una). La razón por la que hago esta pregunta es porque creo que tengo un algoritmo que resuelve ciertas instancias del problema, es decir, con N no un múltiplo de 2 o 3 (N es el número de reinas) Problema relacionado: ¿podemos considerar que el tamaño de entrada es N (donde N es el número de reinas)? ¿O consideramos que el tamaño de entrada es log (N), ya que el número 'N' puede representarse en bits de log (N)?

cc.complexity-theory np-hardness csp Anshul Singhle
fuente

(1) ¿Por qué usas N y n? ¿Son la misma variable o variables diferentes? (2) Para cada número entero n excepto para 2 y 3, hay una manera de poner n reinas en el tablero n × n que cumplan la condición n-queen (ver Wikipedia ), por lo que no sé de qué problema estás hablando cuando usted dice "este es un problema NP-difícil".

Tsuyoshi Ito

Recuerdo que hay un resultado de dureza cuando el tablero no es necesariamente cuadrado: es decir, la forma del tablero se da como parte de la entrada.

Sasho Nikolov

No puede haber una prueba de completitud NP para el tablero de ajedrez , porque este problema tiene una entrada unaria ... es decir, solo hay una entrada para el tamaño , mientras que el testigo necesita una descripción de tamaño polinómico. El teorema de Mahaney dice que mostrar un problema como este para completar NP implicaría que P = NP. Necesita formas de tablero divertidas para que el problema sea NP-completo.

n \times n

$n \times n$

n

$n$

Peter Shor

Quizás contar las soluciones es un problema un poco más interesante (más allá de la clase #P como se demostró en "Sobre la dureza de contar problemas de mapeos completos").

Marzio De Biasi

Ver también: dl.acm.org/citation.cfm?id=122322

Jeffε

Respuestas:

Como se dijo, la respuesta a esta pregunta es NO.

Referencias: Un algoritmo de tiempo polinomial http://dl.acm.org/citation.cfm?id=101343 [cortesía: vzn]

Otra técnica mucho más simple: http://dl.acm.org/citation.cfm?id=122322 [cortesía: Jeffe]

Anshul Singhle
fuente

puede considerar aceptar esta respuesta para que no vuelva a aparecer como sin respuesta.

Suresh Venkat

No se garantiza que el algoritmo de tiempo polinómico en la primera referencia produzca una solución. Si el algoritmo tiene éxito o no depende de la configuración inicial, que se elige al azar, y los autores solo dan evidencia empírica de que parece tomar un número polinómico de ensayos hasta que tiene éxito.

Tsuyoshi Ito

La segunda referencia tampoco es una prueba. El hecho de que se encuentre una única solución factible para n-reinas con n = 500000, no significa que esté en P. (solo lo hace más probable)

Geoffrey De Smet

En realidad, se acaba de demostrar que este es el caso.

https://blogs.cs.st-andrews.ac.uk/csblog/2017/08/31/n-queens-completion-is-np-complete/ ]

Kasper
fuente

N

$N$

@ClementC. En realidad, dado que la pregunta original no es lo suficientemente precisa, creo que Kasper tiene razón incluso si su forma de decirlo puede ser incompleta. Decidir, dado n, si existe una ubicación está claramente en P ya que el problema siempre tiene soluciones para n> 3. Por lo tanto, el problema de finalización de n-reinas (decidir si se puede ampliar una solución parcial dada) parece un problema de decisión natural para comprender la complejidad del problema.

holf

@holf Eso es de hecho un punto válido que haga, pero que esta respuesta ni siquiera menciona (y que un lector absolutamente no llegaría al leerlo). Tener una respuesta engañosa a una pregunta ambigua no es exactamente óptimo.

Clemente C.